LeetCode 1123 - Lowest Common Ancestor of Deepest Leaves

LeetCode Problem 1123

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to find the lowest common ancestor, abbreviated as LCA, of all the deepest leaf nodes in a binary tree.

A leaf node is any node with no children. The depth of the root is 0, and every level downward increases the depth by 1. The deepest leaves are therefore the leaf nodes located at the maximum depth in the tree.

The lowest common ancestor of a set of nodes is the deepest node in the tree that contains all of those nodes inside its subtree. A node is considered part of its own subtree, so if there is only one deepest leaf, that leaf itself is the answer.

The input is the root of a binary tree. The output should be the actual tree node representing the LCA of all deepest leaves.

For example, consider this tree:

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

The deepest leaves are 7 and 4, both at depth 3. Their lowest common ancestor is node 2, because 2 is the deepest node whose subtree contains both leaves.

The constraints are relatively small, with at most 1000 nodes. This means even moderately expensive approaches could pass, but the problem strongly suggests that a clean depth-first search solution exists.

Several edge cases are important:

• A tree with only one node, the root is both the deepest leaf and the answer.
• A completely skewed tree, where the deepest leaf lies entirely on one side.
• Multiple deepest leaves spread across both left and right subtrees.
• A subtree where one side is deeper than the other, meaning the answer should propagate upward from the deeper side rather than the current node.

Because all node values are unique, we never need to worry about ambiguity when identifying nodes.

Approaches

Brute Force Approach

A brute force solution would first determine the maximum depth of the tree, then collect all leaf nodes at that depth. After gathering the deepest leaves, we could repeatedly compute pairwise LCAs until only one node remains.

One possible implementation is:

1. Perform a DFS or BFS to compute the maximum depth.
2. Traverse again to collect all deepest leaves.
3. For every pair of deepest leaves, compute their LCA using parent pointers or recursive traversal.
4. Reduce the set until a single common ancestor remains.

This approach works because the LCA operation is well defined, and combining LCAs pairwise eventually produces the common ancestor of the entire set.

However, this solution is inefficient because each LCA computation may require traversing large portions of the tree repeatedly. If there are many deepest leaves, the repeated searches become unnecessarily expensive.

Optimal Approach

The key insight is that we can compute both the deepest depth and the correct ancestor simultaneously during a single postorder DFS traversal.

For every node, we ask:

• What is the deepest depth reachable from this node?
• Which node is the LCA of the deepest leaves in this subtree?

The recursive logic becomes elegant:

• If the left and right subtrees have the same maximum depth, then the current node is the LCA of the deepest leaves below it.
• If one side is deeper, then the answer must lie entirely in that deeper subtree.

This works naturally because the recursion processes children before parents, which matches the structure of the LCA problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(N)	Multiple traversals and repeated LCA computations
Optimal	O(N)	O(H)	Single DFS traversal returning depth and ancestor together

Here, N is the number of nodes and H is the tree height.

Algorithm Walkthrough

1. Define a recursive DFS function that processes one subtree at a time.

The function should return two values:

• The depth of the deepest leaf in the current subtree
• The LCA of all deepest leaves in the current subtree

2. Handle the base case for a null node.

A null subtree contributes no depth and no ancestor. We can return:

depth = 0
ancestor = null

3. Recursively process the left subtree.

The recursive call gives:

• The maximum depth reachable on the left
• The LCA for the deepest leaves on the left side

4. Recursively process the right subtree.

Similarly, we obtain:

• The maximum depth reachable on the right
• The LCA for the deepest leaves on the right side

5. Compare the left and right depths.

There are three cases:

• If the left depth is greater, the deepest leaves exist entirely in the left subtree. Return the left ancestor.
• If the right depth is greater, the deepest leaves exist entirely in the right subtree. Return the right ancestor.
• If the depths are equal, deepest leaves exist on both sides. The current node becomes their lowest common ancestor.

6. Add one to the larger depth before returning.

Since the current node sits one level above its children, we increment the depth as recursion unwinds upward. 7. Start DFS from the root and return the ancestor component of the result.

Why it works

The algorithm maintains an important invariant:

For every subtree, the recursive function correctly returns the deepest depth within that subtree and the LCA of all deepest leaves contained there.

If both subtrees have equal depth, then deepest leaves exist on both sides, so the current node must be the lowest node connecting them. If one subtree is deeper, then all deepest leaves lie entirely inside that subtree, so its ancestor remains valid. Because recursion processes children before parents, every node makes its decision using already-correct subtree information.

Python Solution

# 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

from typing import Optional, Tuple

class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        def dfs(node: Optional[TreeNode]) -> Tuple[int, Optional[TreeNode]]:
            if not node:
                return 0, None
            
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            
            if left_depth > right_depth:
                return left_depth + 1, left_lca
            
            if right_depth > left_depth:
                return right_depth + 1, right_lca
            
            return left_depth + 1, node
        
        return dfs(root)[1]

The implementation follows the recursive strategy directly.

The dfs function returns a tuple containing:

• The maximum depth reachable from the current node
• The LCA of deepest leaves in that subtree

The base case handles null nodes by returning depth 0 and no ancestor.

For each non-null node, the algorithm recursively computes information for the left and right children. After obtaining both results, it compares the subtree depths.

If one subtree is deeper, the deepest leaves must lie entirely there, so the corresponding LCA propagates upward unchanged.

If both depths are equal, the deepest leaves exist in both subtrees, meaning the current node is the first point where they meet. Therefore, the current node becomes the LCA.

Finally, the main function returns only the ancestor portion from the root call.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func lcaDeepestLeaves(root *TreeNode) *TreeNode {

    var dfs func(node *TreeNode) (int, *TreeNode)

    dfs = func(node *TreeNode) (int, *TreeNode) {
        if node == nil {
            return 0, nil
        }

        leftDepth, leftLCA := dfs(node.Left)
        rightDepth, rightLCA := dfs(node.Right)

        if leftDepth > rightDepth {
            return leftDepth + 1, leftLCA
        }

        if rightDepth > leftDepth {
            return rightDepth + 1, rightLCA
        }

        return leftDepth + 1, node
    }

    _, lca := dfs(root)
    return lca
}

The Go implementation mirrors the Python logic closely.

Instead of tuples, Go functions naturally return multiple values. The recursive helper returns an integer depth and a pointer to the ancestor node.

Go uses nil instead of Python's None for missing nodes. Since the problem constraints are small, recursion depth is safe and no special stack handling is necessary.

Worked Examples

Example 1

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

Deepest leaves are 7 and 4.

We process bottom-up.

Node	Left Depth	Right Depth	Returned LCA	Returned Depth
6	0	0	6	1
7	0	0	7	1
4	0	0	4	1
2	1	1	2	2
5	1	2	2	3
0	0	0	0	1
8	0	0	8	1
1	1	1	1	2
3	3	2	2	4

Final answer is node 2.

Example 2

Input:
    1

Only one node exists.

Node	Left Depth	Right Depth	Returned LCA	Returned Depth
1	0	0	1	1

The root itself is the deepest leaf and therefore the answer.

Example 3

Input:
    0
   /
  1
   \
    2

Node 2 is the only deepest leaf.

Node	Left Depth	Right Depth	Returned LCA	Returned Depth
2	0	0	2	1
1	0	1	2	2
0	2	0	2	3

Final answer is node 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited exactly once
Space	O(H)	Recursive call stack stores at most one path from root to leaf

The algorithm performs a single DFS traversal. Each node contributes constant work, consisting mainly of comparing subtree depths and selecting the correct ancestor. Therefore, total runtime is linear in the number of nodes.

The space complexity comes entirely from recursion. In the worst case of a skewed tree, the recursion depth becomes N. In a balanced tree, it remains O(log N).

Test Cases

# Definition for testing
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):
        
        def dfs(node):
            if not node:
                return 0, None
            
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            
            if left_depth > right_depth:
                return left_depth + 1, left_lca
            
            if right_depth > left_depth:
                return right_depth + 1, right_lca
            
            return left_depth + 1, node
        
        return dfs(root)[1]

sol = Solution()

# Example 1
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

assert sol.lcaDeepestLeaves(root).val == 2  # deepest leaves split under node 2

# Example 2
root = TreeNode(1)

assert sol.lcaDeepestLeaves(root).val == 1  # single-node tree

# Example 3
root = TreeNode(0)
root.left = TreeNode(1)
root.left.right = TreeNode(2)

assert sol.lcaDeepestLeaves(root).val == 2  # only one deepest leaf

# Perfect binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

assert sol.lcaDeepestLeaves(root).val == 1  # deepest leaves on both sides

# Left-skewed tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(4)

assert sol.lcaDeepestLeaves(root).val == 4  # deepest leaf is itself

# Right-skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)

assert sol.lcaDeepestLeaves(root).val == 3  # deepest node on right chain

# Deepest leaves entirely in left subtree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

assert sol.lcaDeepestLeaves(root).val == 2  # deepest leaves under left subtree only

# Uneven depths
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
root.right = TreeNode(3)

assert sol.lcaDeepestLeaves(root).val == 4  # one deepest node

# Balanced deeper tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

assert sol.lcaDeepestLeaves(root).val == 1  # all deepest leaves share root

Test	Why
Single node tree	Smallest valid input
Perfect binary tree	Deepest leaves split evenly
Left-skewed tree	Maximum recursion depth on one side
Right-skewed tree	Symmetric skew case
Deepest leaves in left subtree	Ensures ancestor propagates upward
Uneven depths	Confirms single deepest leaf handling
Balanced deeper tree	Tests global LCA at root
Problem examples	Validates expected outputs

Edge Cases

Single Node Tree

A tree containing only the root node is an important boundary condition. A naive implementation might incorrectly return None because there are no child nodes to compare. In this implementation, the leaf node returns itself as the ancestor when both subtree depths are equal at zero, so the root is correctly returned.

Completely Skewed Tree

In a tree shaped like a linked list, all nodes have only one child. The deepest leaf is unique, so the answer should be that leaf itself. Some incorrect solutions mistakenly return the root because they assume an ancestor must involve multiple branches. This implementation correctly propagates the deepest subtree ancestor upward unchanged.

Multiple Deepest Leaves Across Different Subtrees

When deepest leaves exist on both the left and right sides of a node, that node becomes the true lowest common ancestor. This is the core scenario of the problem. The implementation handles it by checking when left and right depths are equal and returning the current node.

Deepest Leaves Entirely Inside One Subtree

A subtle case occurs when both deepest leaves are contained completely within one subtree. The current node should not become the ancestor merely because it connects the entire tree. By comparing subtree depths, the algorithm correctly ignores shallower branches and preserves the deeper subtree's ancestor result.