Lowest Common Ancestor: Binary Tree and BST Approaches

To find the Lowest Common Ancestor in a binary tree, you must use a recursive post-order traversal that returns the node itself or null. If you are working with a Binary Search Tree, you should ignore the general tree approach and use the node values to prune your search path.

The Binary Tree approach

When you face a generic binary tree, you have no information about where a node might exist relative to its parent. You must search both the left and right subtrees. The logic is simple: if the current node is null, or if it matches one of the two target nodes, return it. Otherwise, recurse on both children. If both recursive calls return a non-null value, the current node is your ancestor. If only one returns a value, pass that value up the stack.

Consider a tree where the root is 3, with left child 5 and right child 1. If you look for the LCA of 5 and 1, the root 3 receives 5 from the left and 1 from the right. Since both sides returned a value, 3 is the LCA. This O(n) approach is necessary because you cannot predict which branch contains your targets.

The BST shortcut

A Binary Search Tree is different because the values are ordered. If both target nodes are smaller than the current node, the LCA must be in the left subtree. If both are larger, it must be in the right subtree. If one is smaller and one is larger, or if the current node matches one of the targets, you have found the LCA.

This logic turns an O(n) search into an O(h) search, where h is the height of the tree. In a balanced BST, this is O(log n). Never use the generic binary tree recursion for a BST problem. It is inefficient and signals to an interviewer that you are not thinking about the properties of the data structure.

Distance between nodes

Once you find the LCA, calculating the distance between two nodes becomes a simple path-length problem. The distance between node p and node q is the distance from p to the LCA plus the distance from q to the LCA. You can write a helper function getDepth(root, target, depth) that returns the depth of a node. If p is at depth 2 and q is at depth 3, and their LCA is at depth 1, the distance is (2 - 1) + (3 - 1), which equals 3.

Quick reference rules

• Use post-order recursion for generic binary trees to bubble up results.
• Use the BST property (left < root < right) to prune branches and save time.
• If the problem asks for distance, find the LCA first, then sum the depths.
• Always check if the root is null or matches a target node as your base case.

A worked example

Take a BST with root 10, left child 5, and right child 15. Let the left child of 5 be 2, and the right child of 5 be 8. You want the LCA of 2 and 8. Start at 10. Since 2 and 8 are both less than 10, move to 5. Now, 2 is less than 5 and 8 is greater than 5. Because the targets split at 5, the node 5 is the LCA. The distance from 5 to 2 is 1, and the distance from 5 to 8 is 1. The total distance is 2.

Practice these patterns on DSA Tracker by filtering for tree problems and specifically comparing the recursive and iterative solutions for the same input.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.