DSA sheet · Trees · Lowest Common Ancestor pattern

Lowest Common Ancestor of a Binary Tree

This is the first problem of the LCA pattern, and the next problems (like LCA of Deepest Leaves) build directly on it. Given two nodes, we must find the closest node above both of them. The teacher does not hand us the code. She tries small "what if" cases one by one, and each case adds one line to the solution. Then she shows a second approach using the parent map from the previous video (Nodes at Distance K) and explains why the first one is preferred in interviews.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Words you must know first
• Part A · LCA with recursive DFS (the main approach)
• Part B · LCA with a parent map and a set (second approach)
• Part C · Revision page

Part 0 · Before starting

• Ancestor: any node on the path from a node up to the root: its parent, its grandparent, and so on. By LeetCode's definition, a node is also an ancestor of itself.
• Common ancestor of p and q: a node that is an ancestor of both.
• Lowest common ancestor (LCA): of all common ancestors, the one deepest in the tree (closest to p and q, furthest from the root). "Lowest" means lowest on the page, not smallest value.

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

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

Part A · LCA with recursive DFS

LeetCode 236

1The question in simple words

You get the root of a binary tree and two nodes p and q that are both in the tree. Return their lowest common ancestor: the deepest node that has both p and q somewhere below it (or is one of them).

The teacher's examples on the tree above:

• p = 5, q = 1 → 3. 5 and 1 hang on different sides of 3, and 3 is the only node above both.
• p = 6, q = 2 → 5. Both 5 and 3 are above 6 and 2, so both are common ancestors. But 3 is like the grandparent, and 5 is the closer one, so the lowest one is 5.
• p = 5, q = 8 → 3. The parent of 5 is 3 and the parent of 8 is 1. 1 is not above 5, so we keep going up to 3. So the answer isn't "always the direct parent". It is the first node that sits above both.

2What the constraints tell us

• Number of nodes: 2 to 10⁵ → at least 2, because p and q must both exist. So the tree is never empty.
• 10⁵ nodes is big. O(n²) would be 10¹⁰ operations, and anything beyond about 10⁸ risks TLE. So we must aim for O(n), a single pass.
• Values go up to 10⁹ in size. That still fits in a normal int (in Java you'd only need long for bigger numbers). Also, we never add or multiply values, so there's no overflow risk at all. In Python it never matters anyway.
• All values are unique, p ≠ q, and both p and q are in the tree.

The smallest case: a node can be its own ancestor

   1           1
  /             \
 2               2

With only 2 nodes and p = 1, q = 2: the parent of 2 is 1, and 1 counts as its own ancestor. So the answer is 1, in both shapes. The point: the answer can be p or q itself. It doesn't have to be a third node sitting above them.

3Intuition: ask each subtree "did you find anyone?"

Stand at a node and send two messengers down: one into the left subtree, one into the right. Each messenger comes back and reports either "I found p or q (here it is)" or "I found nothing".

• If both messengers found something, then p is on one side and q is on the other. You are the split point: you are the LCA.
• If only one found something, the answer is somewhere down that side. Just pass its report up.
• If neither found anything, report "nothing" upwards.

In code, "found something" means returning a node, and "found nothing" means returning None.

4Building the conditions from examples

Case 1: the root itself is p (or q) → return the root

Say p = 3 (the root) and q = 0. The LCA is 3: 3 is above 0, and 3 is its own ancestor. Now the teacher asks: once we've found 3, do we even need to look further down? No. Whatever is below, the answer is already 3.

This is true for any node, not just the real root: if the current node equals p or q, return it straight away.

Case 2: p and q are on different sides → the root is the LCA

Say p = 5, q = 1. At 3: it's neither p nor q, so we go left and go right.

• Going left, we reach 5. 5 is p → Rule 1 returns 5. So 3's left messenger brings back 5.
• Going right, we reach 1. 1 is q → Rule 1 returns 1. So 3's right messenger brings back 1.

The left side says "I found one!" and the right side says "I found one too!". The teacher pictures 3 telling them: don't argue, I'm the common parent.

Case 3: the empty spot → return None

When we go past a leaf we land on None. There's nothing to find there, so we return None. Since root is None in that case, "return None" is the same as "return root". So the teacher folds it into Rule 1:

Case 4: p = 6, q = 4 → both None, or only one side found something

The answer should be 5. Let's follow it:

• At 3: not p or q → go left to 5. At 5: not p or q → go left to 6.
• 6 is p → return 6. So 5's left = 6.
• 5 goes right to 2. 2 is not p or q → go left to 7. 7 is not p or q → its left and right are both None → both return None.

Both sides of 7 are None. What should 7 return? It's not p or q, and nothing was found below it. So it reports "nothing" → None. Returning a node means "I found it", so we may only return a node when we really found one.

• So 2's left = None. 2 goes right to 4. 4 is q → return 4. So 2's right = 4.

Now 2 has left = None, right = 4. This is a new case. 2 is not the LCA, but it must pass the 4 upwards, because 5 is waiting for a "found" report from its right side. Without it, 5 could never announce itself.

• So 2 returns 4. Now 5 has left = 6 and right = 4 → both found → 5 returns itself.
• 3 gets left = 5 and right = None (nothing on the 1 side) → only one side found something → pass 5 up. Answer 5 ✓.

The same goes for the mirror case: if 7 had been q instead of 4, the left side would bring the node back and the right side would bring None, and 2 would pass up the left one.

Writing Rule 3 in one line

The teacher compresses the last part into a single line: return left if left is not None else right. Why does it cover every case?

5Approach steps

1. If the node is None, or is p, or is q → return it.
2. Ask the left subtree, and ask the right subtree (two recursive calls). Save both answers.
3. If both answers are nodes → p and q are split across this node → return this node.
4. Otherwise return whichever answer is not None (or None if both are None).

6Code (Python)

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None or root is p or root is q:   # Rule 1
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left is not None and right is not None:   # Rule 2: split here
            return root
        return left if left is not None else right   # Rule 3

We compare nodes with is (the very same node object), because LeetCode gives us p and q as nodes from this tree. Comparing values with == also works here because the values are unique.

7Code line by line

8Dry run using the call stack

Run 1: p = 5, q = 1

1. f(3): not None, not 5, not 1 → call left. f(3) waits.
2. f(5): 5 is p → return 5. f(5) leaves the stack. f(3).left = 5.
3. f(3) calls right: f(1): 1 is q → return 1. f(3).right = 1.
4. f(3): left = 5, right = 1, both found → return 3. Answer 3 ✓

Run 2: p = 6, q = 4

1. f(3) → no match → go left. f(5) → no match → go left.
2. f(6): 6 is p → return 6. f(5).left = 6.
3. f(5) goes right: f(2) → no match → go left: f(7) → no match.
4. f(7) calls f(None) twice → None, None → returns None. f(2).left = None.
5. f(2) goes right: f(4): 4 is q → return 4. f(2).right = 4.
6. f(2): left None, right 4 → return 4. f(5).right = 4.
7. f(5): left 6, right 4 → both found → return 5. f(3).left = 5.
8. f(3) goes right: f(1) → f(0) and f(8) both give None (their children are None) → f(1) returns None.
9. f(3): left 5, right None → return 5. Answer 5 ✓

9Complexity & remember

• Time O(n): in the worst case every node is visited once.
• Space O(h) for the recursion stack, where h = height. The stack only ever holds one path from the root down, about one node per level. For a balanced tree that's O(log n). For a skewed tree (a straight line) it's O(n).

Part B · LCA with a parent map and a set

The teacher calls this second approach very basic and very common. It is how you'd find the LCA by hand: walk up from p to the root, walk up from q, and see where the two paths first meet.

1The question (same as Part A)

Same input, same output. Only the method changes.

2Constraints (same as Part A)

n up to 10⁵ → still must be O(n). This approach is O(n) too, but uses more memory (we'll see why that matters at the end).

3Intuition: two paths up to the root

Write down every node on the way from p up to the root. Then walk up from q. The first node on q's way up that's already on p's list is the LCA.

• p = 6, q = 8: path of 6 = 6 → 5 → 3. Path of 8 = 8 → 1 → 3. The first shared node is 3.
• p = 6, q = 4: path of 6 = 6 → 5 → 3. Path of 4 = 4 → 2 → 5 → 3. Walking up from 4: 4 no, 2 no, 5 yes → answer 5.

But there's a problem: trees only go down. From 6 we can't step up to 5. The fix is the one from the previous video (Nodes at Distance K): build a parent map first, so every node can look up its parent.

4Building the logic

Step 1: the parent map (DFS)

Exactly as before: start at the root with parent None. Store parent[node] = par, then call the left child and the right child with the current node as their parent. On our tree: 3 → None, 5 → 3, 1 → 3, 6 → 5, 2 → 5, 7 → 2, 4 → 2, 0 → 1, 8 → 1.

This is the only recursive part of this approach. The rest is two simple while loops.

Step 2: store all of p's ancestors in a set

Start at p, add it to a set, and jump to its parent. Repeat until we fall off the top. That happens right after the root, because parent[root] is None. So the loop is while p is not None.

For p = 6: add 6 → jump to 5 → add 5 → jump to 3 → add 3 → jump to None → stop. Set = {6, 5, 3}.

Step 3: walk up from q until we hit the set

Start at q. While q is not in the set, jump to its parent. The moment q is in the set, it's the first node shared by both paths: the LCA. Return it.

For q = 4: is 4 in {6, 5, 3}? No → go to 2. Is 2 in it? No → go to 5. Is 5 in it? Yes → stop → return 5 ✓.

5Approach steps

1. Build parent with a DFS from the root (root's parent = None).
2. Walk from p up to the root, adding every node to a set ancestors.
3. Walk from q upwards until q is in ancestors.
4. Return q.

6Code (Python)

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        parent = {}
        self.buildParent(root, None, parent)

        ancestors = set()
        while p is not None:          # p, its parent, ..., the root
            ancestors.add(p)
            p = parent[p]

        while q not in ancestors:     # climb from q until the paths meet
            q = parent[q]
        return q

    def buildParent(self, node, par, parent):
        if node is None:
            return
        parent[node] = par
        self.buildParent(node.left, node, parent)
        self.buildParent(node.right, node, parent)

7Code line by line

8Dry run

p = 6, q = 4

p = 6, q = 8

Set = {6, 5, 3}. Climb from 8: 8 no → 1 no → 3 yes → return 3 ✓.

9Complexity: why Part A is preferred

• Time O(n): building the map visits every node, O(n). The two while loops only climb one path each, so they cost O(h). The teacher calls this O(log n), which is true for a balanced tree. For a skewed tree h can be n, but it's still added, not multiplied. Total: O(n).
• Space O(n): the parent map holds every node, plus the set, plus the recursion stack while building the map.

Both approaches are O(n) time, but this one needs an extra hash map and hash set. Part A only uses the recursion stack. So in an interview, the recursive DFS (Part A) is the one the interviewer expects. Part B is good to know because the "parent map" trick comes back in other problems.

Part C · Revision page

def T(v, l=None, r=None):
    n = TreeNode(v); n.left, n.right = l, r; return n
n6, n7, n4, n0, n8 = T(6), T(7), T(4), T(0), T(8)
n2 = T(2, n7, n4); n5 = T(5, n6, n2); n1 = T(1, n0, n8)
root = T(3, n5, n1)

s = Solution()
print(s.lowestCommonAncestor(root, n5, n1).val)   # 3
print(s.lowestCommonAncestor(root, n6, n4).val)   # 5
print(s.lowestCommonAncestor(root, n5, n4).val)   # 5 (p is above q)
print(s.lowestCommonAncestor(root, n6, n8).val)   # 3

Based on this video: Lowest Common Ancestor of a Binary Tree