The Meeting Point

Given a tree and two nodes P and Q. The Lowest Common Ancestor (LCA) is the deepest node that has both P and Q as descendants.

1. The Logic

We use Postorder Traversal (Bottom-Up). At any node root:

  1. If root is P or Q, return root.
  2. Recurse Left and Right.
  3. Result:
    • If Left & Right both return non-null, root is the LCA.
    • If only one returns non-null, propagate that up.

2. Interactive: LCA Finder

Select two nodes (P and Q) and see where their paths merge.

Select P...

3. Implementation

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) return root;

  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);

  if (left != null && right != null) return root; // Found split point

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

Go

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil || root == p || root == q {
    return root
  }
  left := lowestCommonAncestor(root.Left, p, q)
  right := lowestCommonAncestor(root.Right, p, q)

  if left != nil && right != nil {
    return root
  }
  if left != nil {
    return left
  }
  return right
}