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? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
