Lowest Common Ancestor

Table of Contents +

This is one of those tree questions that looks hard at first but is actually simple. The interviewer wants to see if you understand how recursion can carry information back up a tree. The word “ancestor” can sound confusing, so let me explain it. Then we solve the problem together.

🌳 The Problem

You are given a binary tree and two nodes in it, say p and q. You have to find their lowest common ancestor. The lowest common ancestor is the deepest node that has both p and q somewhere below it. A node can also be its own ancestor, so if p sits below q, then q itself is the answer.

Think of a family tree. Riya and Arjun are cousins. Their lowest common ancestor is the closest grandparent that both of them come from. Not the great-great-grandparent at the top. The closest one. That is the same idea here.

Tree:
            3
          /   \
         5      1
       /  \    /  \
      6    2  0    8
          / \
         7   4

Input:  p = 5, q = 1
Output: 3        (3 is the deepest node with both 5 and 1 under it)

Input:  p = 5, q = 4
Output: 5        (5 is an ancestor of 4, and a node can be its own ancestor)

🐢 The Simple Approach (and why it is slow)

The first idea most people get is to find the full path from the root down to p, then the full path from the root down to q. Now you have two paths. You walk both paths together from the top and the last node where they still match is the answer.

This works. But see, you make two separate trips down the tree to build the paths, and you store both full paths in extra lists. It feels clumsy in an interview. There is a cleaner way that does everything in one single pass.

⚡ The Optimal Approach (one clean recursion)

Here is the key idea. We let the recursion search the tree, and each call simply reports back what it found below it.

If the current node is null, there is nothing here, so return null.
If the current node is p or q, we found one of our targets, so return that node right away.
Otherwise, ask the left side and the right side the same question.
Now look at the two answers that come back. If both sides return non-null, it means one target was found on the left and the other on the right. So the current node is the split point. The current node is the answer.
If only one side returns non-null, both targets live on that one side, so just pass that answer upward.

That is the whole trick. The node where the two searches meet is exactly the lowest common ancestor.

Note

Notice we never compare values or measure depth. The first node that sees one target coming up from its left and the other coming up from its right is automatically the deepest common ancestor. The recursion handles the “deepest” part for free.

Steps to find the LCA

If the node is null or equals p or q, return the node itself.
Recurse into the left subtree and store the result.
Recurse into the right subtree and store the result.
If both left and right results are non-null, return the current node. It is the LCA.
Otherwise, return whichever side is non-null (or null if both are empty).

Now here is that logic written in all five languages.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Returns the lowest common ancestor of p and q.
def lca(root, p, q):
    if root is None or root is p or root is q:
        return root                 # found a target or hit the end

    left = lca(root.left, p, q)
    right = lca(root.right, p, q)

    if left and right:
        return root                 # targets split here, so this is the LCA

    return left if left else right  # pass up the side that found something

# Build the tree from the example
root = Node(3)
root.left = Node(5)
root.right = Node(1)
root.left.left = Node(6)
root.left.right = Node(2)
root.right.left = Node(0)
root.right.right = Node(8)
root.left.right.left = Node(7)
root.left.right.right = Node(4)

p = root.left          # node 5
q = root.right         # node 1
print("LCA of 5 and 1:", lca(root, p, q).val)

The output of the above code will be:

LCA of 5 and 1: 3

⏱️ Time and Space Complexity

We visit each node at most once, so the time is linear in the number of nodes. The space comes from the recursion stack, which grows as deep as the tree.

Approach	Time	Space
Two paths from root, then compare	O(n)	O(n)
Single recursion (optimal)	O(n)	O(h)

Here n is the number of nodes and h is the height of the tree. The optimal version still touches every node, but it does not store any extra paths. It only uses the call stack, which is much smaller.

Tip

If the interviewer says the tree is a Binary Search Tree, mention the faster trick. In a BST you can compare values: if both p and q are smaller than the current node go left, if both are bigger go right, otherwise the current node is the LCA. That runs in O(h) time without checking the whole tree.

🧩 Key Takeaways

✅ The lowest common ancestor is the deepest node that has both target nodes below it, and a node can be its own ancestor.
✅ The clean solution is one recursion that returns a node up the tree when it finds a target.
✅ When both the left and right calls return non-null, the current node is the split point, so it is the LCA.
✅ When only one side returns non-null, just pass that result upward.
✅ It runs in O(n) time and O(h) space, where h is the height of the tree.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Invert a Binary Tree Next Validate a Binary Search Tree

Share & Connect

Share on LinkedIn