@Juver++: Because the two-inorder-traversals approach is less work than the one-inorder-traversal-plus-scan, since it only processes part of the BST, until it finds the match. Furthermore, it is more elegant, it that it doesn't use an extra array of size n. My guess is that the total stack space required, which could be as small as O(log n) or as large as O(n) depending on the balancedness of the BST, is less than the stack space that would be used by a recursive inorder traversal, since recursive calls must save quite a bit of program state on the stack.
Dave On Jun 29, 1:34 am, juver++ <avpostni...@gmail.com> wrote: > @Dave if we would use stack for your approach, why not to simply make one > inorder traversal for obtaining numbers and then apply classical algorithm? -- 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.
