Lowest Common Ancestor of Deepest Leaves

main.md

Question

Approach

I solved this using a post-order DFS. For every node, I calculated the max depth of its children and tracked the lowest common ancestor of the deepest nodes. When both sides had the same depth, that node was the LCA. The recursion naturally bubbled up the right LCA to return.

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

            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)
            elif right_depth > left_depth:
                return (right_depth + 1, right_lca)
            else:
                return (left_depth + 1, node)

        return dfs(root)[1]

Complexities

• Time: O(n)
• Space: O(n)