Problem Statement in English

You are given the root of a binary tree. The deepest leaves are the leaves that are furthest away from the root.

Your task is to find the lowest common ancestor (LCA) of all the deepest leaves in the tree.

Approach

This is a recursive problem where we need to find the deepest leaves and their lowest common ancestor (LCA). The LCA of two nodes is defined as the lowest node in the tree that has both nodes as descendants.

Best to look at the code.

Solution in Python


class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        lca = None
        maxDepth = 0

        def dfs(node, depth):
            nonlocal lca, maxDepth

            maxDepth = max(maxDepth, depth)
            leftDepth = rightDepth = depth

            if node.left:
                leftDepth = dfs(node.left, depth+1)
            if node.right:
                rightDepth = dfs(node.right, depth+1)

            if leftDepth == rightDepth == maxDepth:
                lca = node

            return max(leftDepth, rightDepth)

        dfs(root, 0)
        return lca

Complexity

  • Time: $O(n)$
    Since we iterate over all nodes in the tree once.

  • Space: $O(n)$
    Since we use a recursive stack to store the nodes.

Mistakes I Made

I did some overcomplicated crap before this :(

And we are done.