1123. Lowest Common Ancestor Of Deepest Leaves

1123. Lowest Common Ancestor of Deepest Leaves

The lowest common ancestor (LCA) of the deepest leaves in a binary tree is a classic problem that tests both tree traversal techniques and logical reasoning. In LeetCode problem 1123 – Lowest Common Ancestor of Deepest Leaves, you are given the root of a binary tree and asked to return the node that is simultaneously the ancestor of all the deepest leaves and the deepest such node possible. Understanding this problem requires a clear grasp of tree depth, leaf identification, and how to efficiently locate the common ancestor without unnecessary recomputation.

Problem Overview

A binary tree consists of nodes where each node has at most two children: a left child and a right child. Day to day, the depth of a node is the number of edges from the root to that node. A leaf is a node with no children. The deepest leaves are those leaves that have the maximum depth in the tree. The goal is to find the LCA of all those deepest leaves. The LCA of a set of nodes is defined as the deepest node that has every node in the set as a descendant (where a node can be a descendant of itself) Surprisingly effective..

It sounds simple, but the gap is usually here.

Take this: consider the following tree:

The deepest leaves are nodes 7 and 8 (depth = 3). Their LCA is node 5, which is also the deepest node that can serve as an ancestor for all deepest leaves.

Understanding Deepest Leaves

To locate the deepest leaves, we first need a way to compute the depth of each node. But a straightforward method is to perform a depth‑first search (DFS) and record the maximum depth encountered. During the same traversal, we can collect all leaf nodes that achieve this maximum depth.

Key points:

Depth calculation: The depth of the root is 0, its children are depth = 1, and so on.
Leaf detection: A node is a leaf if both its left and right children are null.
Maximum depth tracking: While traversing, keep a variable maxDepth that stores the largest depth seen so far and a list deepestLeaves that stores the leaf nodes at that depth.

This brute‑force approach works but requires two passes (one to compute depths, another to find the LCA) and extra storage for the deepest leaves.

Defining Lowest Common Ancestor

The LCA of two nodes in a binary tree is the node furthest from the root that has both nodes as descendants. Extending this to multiple nodes, the LCA of a set is the deepest node that is an ancestor of every node in the set Still holds up..

Important observations:

If the deepest leaves are in different subtrees of a node, that node is a candidate LCA.
If all deepest leaves lie entirely within the left subtree, the LCA must be in the left subtree.
The LCA is unique for a given set of nodes.

Thus, we can find the LCA by simultaneously tracking depth and ancestry during a single traversal.

Approaches

1. Brute Force (DFS + LCA Search)

Perform a DFS to compute the depth of every node.
Identify the maximum depth and collect all leaf nodes at that depth.
For each deepest leaf, find its path from the root.
Compare the paths to locate the common prefix; the last node of this prefix is the LCA.

This method is intuitive but inefficient: it requires O(N) time for depth calculation, O(L) time for path extraction (where L is the number of deepest leaves), and O(N) extra space for storing paths Less friction, more output..

2. One‑Pass DFS (Optimal)

A more elegant solution processes the tree in a single DFS while maintaining two pieces of information for each subtree:

depth: the maximum depth of any node in the subtree.
lca: the candidate LCA for that subtree’s deepest leaves.

The recursion works as follows:

If a node is null, return depth = -1 and lca = null Simple, but easy to overlook. Less friction, more output..
Recursively obtain results from the left and right children.
Determine the larger child depth:
- If left depth > right depth, propagate the left child’s LCA upward.
- If right depth > left depth, propagate the right child’s LCA upward.
- If depths are equal, the current node becomes the LCA because the deepest leaves are spread across both subtrees.

This approach ensures that the final LCA returned from the root is the deepest node that can serve as an ancestor for all deepest leaves.

3. BFS Level Order (Alternative)

Using a breadth‑first search, we can traverse the tree level by level. After completing the traversal, the last level processed contains all deepest leaves. Then, a simple DFS from the root can locate the LCA of the nodes in that level. While BFS avoids recursion, it still requires an extra pass to collect the deepest level nodes and another pass to compute the LCA.

Some disagree here. Fair enough.

Detailed Solution (One‑Pass DFS)

Below is a step‑by‑step explanation of the optimal one‑pass DFS algorithm, followed by a concise Python implementation That's the whole idea..

Algorithm Steps

Define a helper function dfs(node) that returns a tuple (depth, lca) Still holds up..
Base case: If node is null, return (-1, None).
Recursive calls: Obtain (leftDepth, leftLca) and (rightDepth, rightLca) from the left and right children.
Determine current depth: currentDepth = 1 + max(leftDepth, rightDepth).
Select LCA for current subtree:
- If leftDepth > rightDepth: return (currentDepth, leftLca).
- If rightDepth > leftDepth: return (currentDepth, rightLca).
- If leftDepth == rightDepth: the deepest leaves are present in both subtrees, so the current node is the LCA; return (currentDepth, node).
Final result: Call dfs(root) and return its LCA component.

Python Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            # Returns (depth, lca) for the subtree rooted at `node`
            if not node:
                return -1, None

            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)

            # Depth of the current node

is `1 + max(left_depth, right_depth)`.

            if left_depth > right_depth:
                return current_depth, left_lca
            elif right_depth > left_depth:
                return current_depth, right_lca
            else:
                # Depths are equal; current node is the LCA for deepest leaves in this subtree
                return current_depth, node

        _, lca = dfs(root)
        return lca

Complexity Analysis

Time Complexity: $O(N)$, where $N$ is the number of nodes in the tree. Each node is visited exactly once.
Space Complexity: $O(H)$, where $H$ is the height of the tree. This accounts for the recursion stack. In the worst case (a skewed tree), $H = N$; for a balanced tree, $H = \log N$.

Key Insights

The elegance of this solution lies in the realization that the LCA of the deepest leaves is structurally determined by the relative heights of the left and right subtrees. By returning both the height and the candidate LCA simultaneously, we avoid a second traversal. This "bottom-up" propagation of information is a classic pattern for tree problems involving global properties (like diameter, longest path, or deepest nodes) that depend on subtree structure.

Conclusion

Finding the Lowest Common Ancestor of the deepest leaves transforms from a seemingly multi-pass problem into an elegant single traversal by leveraging post-order recursion. The algorithm efficiently computes the answer in $O(N)$ time by maintaining just two pieces of state per node: the maximum depth reachable and the corresponding ancestor. This pattern—returning a tuple of (metric, answer) from a DFS—is a powerful tool applicable to a wide range of binary tree problems where the solution for a parent node depends on the aggregated results of its children.

1123. Lowest Common Ancestor Of Deepest Leaves