Lowest Common Ancestor of a Binary Tree

mediumTrees: BST & Advanced15 stepsJava · Python · C++

Search both subtrees for p and q. A node returns itself if it is p or q; otherwise it returns whatever its subtrees found. The first node that gets a non-null answer from both sides is the LCA.

▶ Watch the animated trace

Traced input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1 → 3. Original problem: neetcode.io/problems/lowest-common-ancestor-of-a-binary-tree

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(h)

Worst case visits every node.

Key idea

Return value means "I found p, q, or their LCA in this subtree".
Both sides non-null: p and q are split here, so this node is the LCA.
One side non-null: pass that result up.
If the current node is p or q, return it immediately; the other can only be below it.

Common mistakes

Assuming p and q are in different subtrees.
Searching each node separately with a contains() helper is O(n²).

Solution

Java

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    TreeNode result = (left != null && right != null) ? root : (left != null ? left : right);
    return result;
}

Python

def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    if not root: return None
    if root is p or root is q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if left and right else (left or right)

C++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (root == p || root == q) {
        return root;
    }
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    return (left && right) ? root : (left ? left : right);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Ancestor of itself The search returns 5 without looking below it.	`root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4`	`5`
Two nodes The root is p.	`root = [1, 2], p = 1, q = 2`	`1`
Deep leaves They meet only at the root.	`root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 7, q = 8`	`3`