Loading...
Traversals, recursion versus iteration, balancing, and lowest-common-ancestor problems.
3 questions in Data Structures & Algorithms.
Recurse post-order and return the node whose left and right subtrees each report back one target; if only one side reports back, propagate that result upwards. This is O(n) time and O(h) stack. A BST lets you descend by value comparison instead, and parent pointers reduce it to list intersection. It also connects recursion to the point an interviewer is testing.
A bare traversal is not enough, because two different trees can produce identical node sequences. Emitting an explicit marker for every absent child makes a preorder walk unambiguous, and reading it back is the same walk consuming tokens in the same order from a single cursor.
Every node must fall inside an open interval inherited from its ancestors, not merely compare correctly against its own two children. Recurse carrying a low and high bound, tightening one of them at each descent, or walk in-order and require the sequence to be strictly increasing.