@Lucifer Looks like Your algo works for all of the my test cases. I am not able to find counter case.
Also we should not Print "Yes" for N<=3 For eg: A = 4,2,6 Then 2 is a root with 4 as left child and 6 as right child. It contains two childs and fails the case. On Dec 30, 1:26 pm, Lucifer <[email protected]> wrote: > @above > > Also i would like to mention that the above algo considers equal > valued elements and assumes that the BST should have the following > property: > > 1) leftChild < = root > 2) rightChild > root > > On 30 Dec, 13:24, Lucifer <[email protected]> wrote: > > > > > @An idea... > > > Let the array of integers be A[N].. > > > If N < = 3, then the answer would be YES. > > > If N > 3, then the following algo will follow: > > // The algo is self explanatory as its just ensuring BST property > > keeping in mind that a parent node has only one child... > > > int left = smallest(A[0], A[1], A[2]) ; > > int right = greatest(A[0], A[1], A[2] ; > > int mid = A[0] + A[1] + A[2] - left - right; > > > int i = 2; > > > while ( ++i < N) > > { > > if (A[i] <= mid && A[i] > left) > > { > > mid = A[i]; > > right = mid; > > } > > else if (A[i] > mid && A[i] <= right) > > { > > mid = A[i]; > > left = mid; > > } > > else > > break; > > > } > > > if ( i == N) > > printf ("YES"); > > else > > print("NO"); > > > On 30 Dec, 12:51, top coder <[email protected]> wrote: > > > > Input : You have been given a sequence of integers. > > > Now without actually constructing BST from the given sequence of > > > integers (assuming the sequence is pre-order) determine if each node > > > of BST has single child (either left or right but not both). > > > Output : YES if given integer sequence corresponds to such a BST. > > > otherwise say NO. > > > > Ex. Say NO for 16,10,8,9,29,27,22. > > > Say YES for 10,19,17,14,15,16 > > > > I know the algo O(N^2) as follows: > > > For every node in array(traverse from left to right), > > > all the other nodes must be less or all the nodes must be greater > > > than it. > > > > But interviewer is expecting O(N). Any ideas?- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
