Lowest Common Ancestor of a Binary Tree

Difficulty: Medium

Problem

Two nodes p and q are present somewhere in a binary tree. Find the deepest node that sits above both of them (or is one of them), and return it. Be careful: a node is allowed to be its own ancestor, so if p lies under q then q itself is the answer.

Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: Node 5 is inside the left subtree of 3 and node 1 is inside its right subtree, so no node lower than 3 can reach both. The answer is 3.

Brute-force approach

There is no separate brute-force phase. The split-point recursion IS the standard solution. (A heavier alternative: computing both root-paths and comparing. Is discussed in the complexity phase.)

Optimal approach

Key insight: Ask every subtree: 'did you find p or q?' The deepest node whose LEFT and RIGHT both answer yes is where the searches meet, the LCA.

Ask every subtree whether it contains p or q. A found target (or decided LCA) travels upward; the deepest node that hears news from BOTH sides is the answer.

Steps

  1. Base case: null finds nothing, return null
  2. If this node IS p or q, return it immediately
  3. Ask the left subtree, then the right subtree
  4. Both returned something? This node is the split point, return it
  5. Otherwise relay whichever side found something (or null)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function lowestCommonAncestor(root, p, q):
    if root is null:
        return null
    if root is ____ or root is ____:
        return ____
    
    left  = lowestCommonAncestor(root.left,  p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if ____ and ____:
        return root
    return ____ or ____

Hints

  • A call ends instantly when it stands on a target. Which two nodes end it, and what do we return?
  • Collect the reports from both subtrees before deciding anything
  • The split point is where BOTH reports are non-null, what does it return?
  • Only one side found something? Relay it: 'left or right' returns whichever is non-null

Complexity questions

What is the time complexity?

O(n): each node is visited at most once. One traversal; each node does constant work combining its two reports. Early returns (on finding p or q) can skip entire subtrees, but worst case is O(n).

What is the space complexity?

O(h): the recursion stack. Just the recursion stack: O(log n) balanced, O(n) skewed. No paths or parent maps are stored.

Once the split point has decided the LCA, what work do the calls ABOVE it still do?

Pure relaying: each does one constant-time combine and passes the node up. Above the split point, one side returns the LCA and the sibling side returns None (it holds neither target, both were already found). Each ancestor's combine is O(1): relay and return.

If this tree were a Binary Search Tree, how could we find the LCA faster?

Walk down from the root: the first node whose value sits BETWEEN p and q is the LCA, O(h), no full search. In a BST, ordering tells you where the targets live: both smaller → go left; both bigger → go right; otherwise you're standing at the split. That's O(h) with O(1) space iteratively: a beautiful payoff of the BST property you just validated.

Check your understanding of Lowest Common Ancestor of a Binary Tree

What exactly is the lowest common ancestor of p and q?

The DEEPEST node that has both p and q somewhere in its subtree. Many nodes may contain both p and q (the root always does). 'Lowest' means deepest. The last point their two root-paths share before splitting apart.

Same tree, p = 5 and q = 4. What is the LCA?

5. Node 4 sits inside 5's subtree (5 → 2 → 4), and a node is an ancestor of ITSELF, so 5 contains both 5 and 4. No deeper node does. The LCA is 5.

During recursion, how do we recognize the LCA?

It's the first node where p is found on ONE side and q on the OTHER, the two searches meet there. Ask every subtree 'did you find p or q?'. A node where the LEFT answer and the RIGHT answer are both non-empty is the split point: the deepest place the searches meet.

A node's left subtree found p, its right subtree found nothing. What does this node return?

Whatever the left returned. It simply RELAYS the find upward. One-sided finds get passed up unchanged. Somewhere above, a node will see reports from BOTH sides, that node is the LCA. Until then, everyone is just a messenger.

Why may a call STOP and return immediately when it reaches p or q, without searching deeper?

Because if the other target is below this node, this node is still the LCA anyway; if not, a higher node will see both sides, correct either way. Say we reach p. Case 1: q is somewhere below p → p contains both, and nothing deeper can, so p IS the LCA. Case 2: q is elsewhere → some ancestor sees p from one side and q from the other. Returning p on sight is correct in both worlds. That's the ancestor-of-itself convention at work.

Related problems

Keep practising