Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A subtree can summarize itself with its height and the smallest node-rooted subtree containing all of its deepest nodes. If the child heights differ, all deepest nodes are on the taller side. If the heights match, their common enclosing subtree must be rooted at the current node.

Approach

Use postorder recursion returning (height, candidateRoot), with (0, null) for an empty subtree.
Obtain the pair from both children. When their heights match, return that height plus one and the current node. For a leaf this correctly chooses the leaf itself.
Otherwise, return the larger height plus one and the candidate from the taller child; nodes on the shorter side cannot be globally deepest within this subtree.
Return the candidate from the root's pair. Each decision preserves exactly the deepest descendants while excluding unnecessary ancestors.

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

            l = dfs(node.left)
            r = dfs(node.right)

            if l[0] == r[0]:
                return l[0] + 1, node
            elif l[0] > r[0]:
                return l[0] + 1, l[1]
            elif r[0] > l[0]:
                return r[0] + 1, r[1]

        return dfs(root)[1]

Complexity analysis

For N nodes and tree height H, postorder DFS visits every node once, giving O(N) time and O(H) recursion space.