maintain two arrays: one for flags of nodes - true if both of the children nodes satisfy bst condition otherwise false is not. Do it in BFS manner.If after bst condition check, false set for a node then dont parse it down. And for true nodes check down the subtrees and put flags flags till get true or leaf node.
Now while traversing keep an array of parent nodes of each traversed node whether it is false or true. After complete traversal of tree, for each false nodes , in parent array put all ancestors of it to NULL . The remaining non-NULL nodes in parent array are Binary search subtrees. Traversing only once. time : O(n) and space : n+n =O(n) again. On Wed, Aug 31, 2011 at 7:02 AM, Reynald <[email protected]> wrote: > WAP, Given a Binary Tree, find a sub-tree which is a Binary Search > Tree. Optimize for space & Time > > -- > 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. > > -- ........................ *MOHIT VERMA* -- 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.
