Lowest Common Ancestor of Deepest Leaves

Lowest Common Ancestor of Deepest Leaves

What is this problem about?

In the Lowest Common Ancestor of Deepest Leaves problem, you are given a binary tree. Your goal is to find the lowest common ancestor of all the nodes that are at the maximum depth of the tree. The deepest leaves are the nodes furthest away from the root.

Why is this asked in interviews?

This problem is a fantastic blend of two distinct tree concepts: calculating depth and finding ancestors. Interviewers ask it because it forces candidates to evaluate paths dynamically. You cannot find the LCA until you know what the maximum depth is, so you must write code that either does two passes or smartly combines depth-checking with LCA-bubbling in a single pass.

Algorithmic pattern used

The most optimal solution uses a Single Pass Depth-First Search (DFS) that returns a tuple or pair. The recursive function returns two pieces of information: (Current_Subtree_Depth, LCA_Node_For_This_Subtree). At any node, you look at the results from the left child and right child.

• If left_depth == right_depth: The deepest leaves are split between both sides. The current node is the LCA! You return (left_depth + 1, current_node).
• If left_depth > right_depth: The deepest leaves are only on the left. The LCA must be whatever the left child returned. You return (left_depth + 1, left_LCA).
• If right_depth > left_depth: Return (right_depth + 1, right_LCA).

Example explanation

Tree: root 1, left 2, right 3. 2 has left 4. We want the LCA of the deepest leaves. Deepest leaf is just 4.

• DFS at 4: left depth 0, right depth 0. Returns (1, node 4).
• DFS at 2: left returned (1, node 4). Right is null, returns (0, null). Left depth (1) > Right depth (0). Returns (2, node 4).
• DFS at 3: left/right null. Returns (1, node 3).
• DFS at 1: left returned (2, node 4). Right returned (1, node 3). Left depth (2) > Right depth (1). Root 1 ignores the right side entirely and passes up the left side's LCA. Returns (3, node 4). The final LCA is node 4.

Common mistakes candidates make

Candidates often resort to a two-pass solution: a BFS to find the maximum depth and collect all the deepest leaves, followed by another traversal to find the LCA of that list. While functional, it is bulky and slow. Furthermore, trying to use global variables to track max depth during a single pass can lead to messy state management and bugs if not handled perfectly.

Interview preparation tip

To master the Lowest Common Ancestor of Deepest Leaves interview pattern, get comfortable returning custom Objects or Tuples from your recursive functions. If your recursive function can simultaneously pass up the "score" (depth) and the "winner" (the LCA node), you can solve almost any complex tree aggregation problem in a single elegant sweep.