Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Compare the deepest levels in a node's two child subtrees. If one side is taller, all deepest leaves lie there and its answer can be reused. If both sides are equally tall, the current node is their lowest common ancestor.

Approach

Use postorder recursion returning a depth measure and the ancestor of the deepest leaves. Python returns subtree heights: an empty subtree returns zero, and a real node returns one plus the larger child height. Its passed depth argument is not used in this result. JavaScript instead returns the absolute depth argument at an empty subtree and propagates the larger returned depth unchanged; for a nonempty subtree, this is one beyond its deepest leaf's depth. Since the two child roots are at the same depth, these conventions give identical comparisons. Propagate the deeper child's candidate, or choose the current node on a tie. A leaf selects itself. Return the root call's candidate.

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(d, node):
            if not node: return 0, None

            left_d, left_n = dfs(d + 1, node.left)
            right_d, right_n = dfs(d + 1, node.right)
            
            if left_d > right_d:
                return left_d + 1, left_n
            elif right_d > left_d:
                return right_d + 1, right_n
            else:
                return left_d + 1, node
            
        return dfs(0, root)[1]

Complexity analysis

For N nodes and tree height H, postorder DFS visits each node once, taking O(N) time and O(H) recursion space. Both displayed implementations are recursive, so an allowed depth near 1000 can exceed the language runtime stack.