Pattern Recognition Drill
Medium Advanced Trees
The Problem
Find the LCA of two nodes in a binary tree.
What approach would you use?
Think about it before scrolling down.
Recurse left and right. If both return non-null, current node is LCA. If one is null, return the other. O(n).
Common Trap
For BSTs, you can use the BST property to go left/right more efficiently. But for general trees, full recursion is needed.