The Meeting Point

Imagine you are looking at a massive corporate organizational chart. You need to find the lowest-level manager who oversees both the “Frontend Developer” (Employee P) and the “Backend Developer” (Employee Q). In graph theory, this manager is the Lowest Common Ancestor (LCA).

The LCA of two nodes P and Q in a tree is the deepest node that has both P and Q as descendants (where we allow a node to be a descendant of itself). This concept is fundamental, powering operations from Git branch merging (finding the merge base) to DOM event delegation.

1. The Intuition: “Ask Left, Ask Right, Decide”

To find the LCA in a standard Binary Tree without parent pointers, we must traverse the tree. Since we need information from our children to make a decision at the current node, we use Postorder Traversal (Bottom-Up).

Think of it as delegating the search:

Base Case (The Search Ends): If you (the current root) are null, return null. If you are either P or Q, you report yourself back up the chain.
Ask Left & Right: Recursively ask your left child and right child, “Did you find P or Q in your subtrees?”
Decide:
- If both children report a finding (return non-null), you are the meeting point! You are the LCA.
- If only one child reports a finding, you simply pass that finding up to your parent.
- If neither child finds anything, you return null.

2. Interactive: LCA Finder

Select two nodes (P and Q) below and see where their paths merge. Notice how the paths bubble up to the lowest common node.

Select P...

3. Step-by-Step Execution Example

Let’s trace the algorithm on the tree from the interactive visualization above. Suppose we want to find the LCA of Node 6 and Node 4. The root is Node 3.

Call LCA(3, 6, 4): Neither 6 nor 4. Recurse left to LCA(5) and right to LCA(1).
Left Subtree LCA(5): Not 6 or 4. Recurse left to LCA(6) and right to LCA(2).
- Call LCA(6): It matches P (6)! Return 6 up to Node 5.
- Call LCA(2): Not 6 or 4. Recurse left to LCA(7) and right to LCA(4).
  - Call LCA(7): Not 6 or 4, leaf node. Returns null.
  - Call LCA(4): Matches Q (4)! Returns 4 up to Node 2.
- Back at Node 2: Left returned null, Right returned 4. Node 2 returns 4 up to Node 5.
Back at Node 5: Left returned 6, Right returned 4. Both are non-null! Node 5 is the LCA. It returns 5 up to Node 3.
Right Subtree LCA(1): Doesn’t contain 6 or 4. Returns null.
Back at Node 3: Left returned 5, Right returned null. It returns 5.

The final answer is Node 5.

4. Edge Cases & Technical Realities

Node is Ancestor of Itself: If P = 5 and Q = 4, LCA(5) immediately returns 5 (Base case 1). The algorithm never even explores Node 4. This is perfectly valid because 5 is its own ancestor, and since Q is guaranteed to be in the tree, Q must be in 5’s subtree.
Missing Nodes: The standard algorithm assumes both P and Q exist in the tree. If only P exists, the algorithm will return P (assuming Q was in its subtree, which is false). If there’s a chance a node might be missing, you must either search for both nodes first or modify the traversal to ensure both are encountered before concluding.
Call Stack Limits (Space Complexity): The recursion depth is bounded by the height of the tree H. In the worst case (a perfectly unbalanced, linear tree), the space complexity is O(N), which could cause a Stack Overflow on very large trees (e.g., millions of nodes). In a balanced tree, space complexity is O(log N).
Time Complexity: We visit each node at most once, resulting in O(N) time complexity.

5. Implementation

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  // Base case: null or found one of the targets
  if (root == null || root == p || root == q) return root;

  // Ask Left and Right
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);

  // Decide
  if (left != null && right != null) return root; // Found the meeting point

  return (left != null) ? left : right; // Propagate the found node up
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  // Base case
  if root == nil || root == p || root == q {
    return root
  }

  // Ask Left and Right
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)

  // Decide
  if left != nil && right != nil {
    return root // Found the meeting point
  }
  if left != nil {
    return left // Propagate the found node up
  }
  return right
}

6. Alternative Environments (Variations)

Binary Search Tree (BST): If the tree is a BST, we don’t need a full postorder traversal. We can use the BST property: if both P and Q are less than root, go left. If both are greater, go right. The first node where they split (or one equals the root) is the LCA. This is O(H) time.
Parent Pointers: If tree nodes have parent pointers, this becomes an Intersection of Two Linked Lists problem. Traverse from P to root, storing path nodes in a Set. Then traverse from Q to root; the first node you encounter that is in the Set is the LCA. This takes O(H) time and space.

Lowest Common Ancestor