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

The first idea is the two-roads method: find the road from the root to p, find the road from the root to q, store both, and walk them together; the last node they share is the lowest common ancestor. On the example [3,5,1,6,2,0,8,null,null,7,4] with p = 5 and q = 1 that is 2 + 7 = 9 looks to find the two roads (the second search wanders through 5's whole side before reaching 1), and in the worst case 2n looks, with two roads stored. The reports version below needs one sweep and stores nothing.

Steps

  1. Search from the root for p, remembering the road
  2. Search from the root for q, remembering the road
  3. Walk both roads together from the root
  4. Return the last node they share

Time complexity: O(n) time, up to 2n looks · Space complexity: O(h) for each stored road

Trade-offs

  • Searches the tree twice: 9 looks for the 2-step roads of the example, 2n in the worst case
  • Stores two roads

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
  • A call reports the lowest common ancestor of the targets inside its own subtree, None if there is none: a lone target found below is relayed up unchanged, and so is an answer already found.
  • The problem promises both targets exist in the tree (they may be the same node). If one were missing, this code would return the other target.
  • Short names: the video writes lca for lowestCommonAncestor to fit the board; in the Code Arena keep the function name the template gives you.

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). The early return also saves work: on the example, (5, 1) visits 3 of 9 nodes and (4, 5) visits 5 of 9. This relies on the guarantee that both targets exist in the tree.

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