DSA sheet · Trees · Lowest Common Ancestor pattern

Lowest Common Ancestor of Deepest Leaves

This is the second problem of the LCA pattern. The teacher asks you to first watch the LCA of a Binary Tree video (Problem 21), because this one grows out of it. The twist: nobody gives us p and q. We have to find the deepest nodes ourselves, and there might be 2, 4 or more of them. The teacher first shows the idea that comes to mind straight away (BFS + the old LCA function) and why it's clumsy. Then she builds, step by step, a single DFS that returns two things at once: a node and a height. This "return a pair from the recursion" trick is very useful in many tree problems.

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 · First idea: BFS to the last level + repeated LCA
• Part B · Optimal: one DFS returning (node, height)
• Part C · Revision page

Part 0 · Before starting

• Leaf: a node with no children.
• Depth of a node: how far it is from the root. The root has depth 0, its children depth 1, and so on.
• Deepest leaves: the nodes on the last level of the tree, the ones with the biggest depth. (They are always leaves. If one had a child, the child would be even deeper.)
• Height (as used on this page): the number of nodes on the longest path going down from a node. An empty spot (None) has height 0, a leaf has height 1, and in general height = 1 + max(left height, right height). This is the same formula as Maximum Depth (Problem 7).
• LCA (lowest common ancestor): the deepest node that has all the given nodes below it (or is one of them). See Problem 21.

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

  deepest leaves = 7 and 4   →   answer = 2

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

Part A · First idea: BFS to the last level + repeated LCA

LeetCode 1123 (the same problem as LeetCode 865, Smallest Subtree with all the Deepest Nodes)

1The question in simple words

You get the root of a binary tree. Find all the nodes on the deepest level, and return their lowest common ancestor: the lowest node whose subtree contains all of them.

In the tree above, the deepest level holds 7 and 4. The lowest node above both is 2.

How is it different from Problem 21? There, we were given exactly two nodes, p and q. Here we must discover the nodes ourselves, and there may be more than two.

2What the constraints tell us

• Number of nodes: 1 to 1000 → the tree is never empty. And 1000 is small: even O(n²) = 10⁶ operations is far below the danger zone of about 10⁸ (where TLE starts). The teacher's verdict: an n² solution would pass, just slowly. We still aim for the optimal one.
• Values: 0 to 1000 → small, a normal int is fine (an int holds up to about 10⁹).
• Values are unique.

3Intuition: the idea that comes first

"Deepest level" should immediately remind you of level order traversal (BFS). Walk the tree level by level, and the nodes in the last level are the deepest leaves. Then reuse the LCA function from Problem 21 on them.

The teacher says this idea should come to mind if you know BFS and DFS. It's not the optimal one, but it's a good first step.

4Building it, and where it gets clumsy

Easy case: exactly two deepest leaves

In our tree, BFS gives the last level [7, 4]. Call LCA(root, 7, 4) → 2. Done. That's just Problem 21 with p = 7 and q = 4.

Hard case: more than two deepest leaves

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

  deepest leaves = 6, 2, 0, 8   →   answer = 3

Now the last level has four nodes. Which one is p, and which one is q? LCA only takes two at a time. So we have to do it in rounds:

• LCA(6, 2) = 5, and LCA(0, 8) = 1.
• Then LCA(5, 1) = 3.
• Keep pairing up until only one node is left. That's the answer.

This is why the teacher calls the BFS idea not optimal: you have to call the LCA function again and again, and each call walks the whole tree. She doesn't code it in the video, because it's just two earlier problems glued together. We code it below so you can test it and see the shape.

5Approach steps

1. BFS level by level. Remember the nodes of the last level you process.
2. While more than one node is left: pair them up (1st with 2nd, 3rd with 4th, …) and replace each pair with its LCA. An odd one out just moves to the next round.
3. The single node left is the answer.

6Code (Python)

from collections import deque

class Solution:
    def lcaDeepestLeaves(self, root):
        if root is None:
            return None
        queue = deque([root])
        last = []
        while queue:                        # level order traversal
            last = list(queue)              # nodes of this level
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        while len(last) > 1:                # pair up until one is left
            nxt = []
            for i in range(0, len(last), 2):
                if i + 1 < len(last):
                    nxt.append(self.lca(root, last[i], last[i + 1]))
                else:
                    nxt.append(last[i])     # odd one out waits
            last = nxt
        return last[0]

    def lca(self, root, p, q):              # Problem 21, unchanged
        if root is None or root is p or root is q:
            return root
        left = self.lca(root.left, p, q)
        right = self.lca(root.right, p, q)
        if left and right:
            return root
        return left if left else right

7Code line by line

8Dry run (the four-leaf tree)

On the first tree: last = [7, 4] → LCA(7, 4) = 2 ✓ in one round.

9Complexity & remember

• Time: BFS is O(n). Each LCA call is O(n). With L deepest leaves we make about L − 1 calls, so it's O(n · L). L can be about n/2 in a full tree, so the worst case is O(n²). That passes for n ≤ 1000, but it's not optimal.
• Space O(n): the queue (the last level can hold about n/2 nodes) plus the LCA recursion stack.

Part B · Optimal: one DFS returning (node, height)

1The question (same as Part A)

Same input and output. Now we want to solve it in one pass over the tree.

2What the constraints tell us

The tree has at least 1 node, but the recursion still reaches None children, so we need a base case for None. n ≤ 1000 also means Python's recursion limit (about 1000) is fine in normal cases.

3Intuition: height tells you which side to go

Stand at the root 3 and look at both sides. The left subtree has height 3 (3 → 5 → 2 → 7 has 3 nodes below 3). The right subtree has height only 2. The deepest leaves are always on the taller side. So the answer must be somewhere on the left.

• If the left side is taller → the answer is inside the left subtree.
• If the right side is taller → the answer is inside the right subtree.
• If both sides are equally tall → there are deepest leaves on both sides, so the lowest node covering all of them is the current node itself.

But going top-down we don't know the heights yet. DFS naturally works bottom-up: it hits the None case first, and builds answers on the way back up. So the teacher's plan is to build the answer at every node, from the bottom to the top.

4Building the conditions from the example

Start with only the height

DFS goes 3 → 5 → 6 first. 6 is the first leaf we hit. Its left and right are None, which have height 0. So:

• 6: left 0, right 0 → height 1 goes back to 5.
• 7: 0 and 0 → height 1. 4: 0 and 0 → height 1. Both go back to 2.
• 2: left 1, right 1 → height 1 + max(1, 1) = 2.

Equal heights → this node is the LCA (so far)

Look at 7: left and right heights are equal (0 and 0). So 7's best answer so far is 7 itself. Same for 4, and same for 6.

Look at 2: left height 1, right height 1, equal. There are deepest leaves on both sides of 2 (7 and 4), so 2 is the LCA of its subtree's deepest leaves.

The important idea: we don't know yet which subtree will end up being the deepest one, so every node just computes its best answer so far and hands it upwards.

Different heights → keep the taller side's answer

Now 5 gets: from the left (6) height 1, from the right (2) height 2. The right side is deeper, so the deepest leaves of 5's subtree are on the right. The LCA must come from the right, and that's 2. 5 must not claim the answer for itself.

But wait: if 5 only receives heights, how does it know that "the right side's answer is 2"? It doesn't. So each call must send up two things:

What height do we send up?

The height always counts the current node too, so it's (height of the side we chose) + 1:

• Equal → (root, left_h + 1). Both sides are equal, so either height works.
• Left taller → (left_node, left_h + 1).
• Right taller → (right_node, right_h + 1).

At 5: right taller → (2, 2 + 1) = (2, 3). Notice that 5 is no longer part of the answer, but it still counts in the height. The answer comes from below, while the height measures the full path through 5.

The base case, final form

Since we now return pairs, the empty spot must return a pair too: no node, height 0.

The final answer

The top call dfs(root) returns a pair like (2, 4). We only need the node, so we return dfs(root)[0]. The height is just a helper.

5Approach steps

1. dfs(None) returns (None, 0).
2. For a real node: get (left_node, left_h) from the left child and (right_node, right_h) from the right child.
3. If left_h == right_h → return (root, left_h + 1).
4. If left_h > right_h → return (left_node, left_h + 1).
5. Otherwise → return (right_node, right_h + 1).
6. The answer is the node part of dfs(root).

6Code (Python)

class Solution:
    def lcaDeepestLeaves(self, root):
        return self.dfs(root)[0]          # we only need the node

    def dfs(self, root):
        if root is None:
            return (None, 0)              # no node, height 0

        left_node, left_h = self.dfs(root.left)
        right_node, right_h = self.dfs(root.right)

        if left_h == right_h:             # deepest leaves on both sides
            return (root, left_h + 1)
        if left_h > right_h:              # deepest leaves only on the left
            return (left_node, left_h + 1)
        return (right_node, right_h + 1)  # deepest leaves only on the right

7Code line by line

8Dry run using the call stack

On the main tree. Each line shows what a call returns, in the order DFS finishes them.

1. dfs(6): left (None, 0), right (None, 0) → equal → returns (6, 1) to 5's left.
2. 5 goes right → 2 → 7. dfs(7): 0 and 0 → equal → (7, 1).
3. dfs(4): 0 and 0 → equal → (4, 1).
4. dfs(2): left (7, 1), right (4, 1) → 1 = 1 → (2, 2). 2 claims the answer.
5. dfs(5): left (6, 1), right (2, 2) → right taller → (2, 3). 5 passes on 2.
6. 3 goes right → 1. dfs(0) → (0, 1), dfs(8) → (8, 1).
7. dfs(1): (0, 1) and (8, 1) → equal → (1, 2).
8. dfs(3): left (2, 3), right (1, 2) → left taller → (2, 4).
9. lcaDeepestLeaves returns the node part → 2 ✓

The stack never holds more than one path at a time. 3, 5 and 6 were on it together, and only after 6 returned did 2 get pushed, then 7. It never gets taller than the number of levels.

On the four-leaf tree: 6, 2, 0, 8 each return (x, 1). 5 gets 1 = 1 → (5, 2). 1 gets 1 = 1 → (1, 2). 3 gets 2 = 2 → (3, 3) → answer 3 ✓. It's the same answer as Part A, but in one pass.

9Complexity & remember

• Time O(n): each node is visited exactly once, and does O(1) work with the two pairs it gets back.
• Space O(h): the recursion stack holds one node per level of the current path. The teacher counts it as the number of levels, which is log n for a balanced tree. For a skewed tree it can be n.

Part C · Revision page

T = TreeNode
root = T(3, T(5, T(6), T(2, T(7), T(4))), T(1, T(0), T(8)))
full = T(3, T(5, T(6), T(2)), T(1, T(0), T(8)))
s = Solution()
print(s.lcaDeepestLeaves(root).val)       # 2
print(s.lcaDeepestLeaves(full).val)       # 3
print(s.lcaDeepestLeaves(T(1)).val)       # 1  (single node)
print(s.lcaDeepestLeaves(T(0, T(1, None, T(2)), T(3))).val)   # 2 (one deepest leaf)

Based on this video: Lowest Common Ancestor of Deepest Leaves