Smallest Subtree with all the Deepest Nodes

medium tree dfs lca

Problem

Given the root of a binary tree, the depth of a node is its distance from the root. A node is deepest if it has the largest depth in the whole tree. Return the smallest subtree that contains all the deepest nodes — equivalently, the lowest common ancestor of every deepest node.

Inputroot = [3,5,1,6,2,0,8,null,null,7,4]

Output[2,7,4]

Deepest nodes are 7 and 4; their lowest common ancestor is node 2.

level-order (use null for gaps)

def subtree_with_all_deepest(root):
    def dfs(node):
        if not node:
            return (0, None)
        ld, lnode = dfs(node.left)
        rd, rnode = dfs(node.right)
        if ld == rd:
            return (ld + 1, node)
        return (ld + 1, lnode) if ld > rd else (rd + 1, rnode)
    return dfs(root)[1]

function subtreeWithAllDeepest(root) {
  function dfs(node) {
    if (!node) return [0, null];
    const [ld, lnode] = dfs(node.left);
    const [rd, rnode] = dfs(node.right);
    if (ld === rd) return [ld + 1, node];
    return ld > rd ? [ld + 1, lnode] : [rd + 1, rnode];
  }
  return dfs(root)[1];
}

TreeNode subtreeWithAllDeepest(TreeNode root) {
    return dfs(root).node;
}
private Result dfs(TreeNode node) {
    if (node == null) return new Result(0, null);
    Result l = dfs(node.left), r = dfs(node.right);
    if (l.depth == r.depth) return new Result(l.depth + 1, node);
    return l.depth > r.depth
        ? new Result(l.depth + 1, l.node)
        : new Result(r.depth + 1, r.node);
}

pair<int, TreeNode*> dfs(TreeNode* node) {
    if (!node) return {0, nullptr};
    auto [ld, ln] = dfs(node->left);
    auto [rd, rn] = dfs(node->right);
    if (ld == rd) return {ld + 1, node};
    return ld > rd ? make_pair(ld + 1, ln) : make_pair(rd + 1, rn);
}
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
    return dfs(root).second;
}

Explanation

The deepest nodes are the leaves that sit at the very bottom of the tree. We want the smallest subtree that still contains all of them, which is just their lowest common ancestor (LCA). The clever part is finding it in a single bottom-up pass.

The helper dfs(node) returns two things for each node: the depth of the deepest leaf below it, and the node that is the answer for that subtree. We compute these for the left and right child first, then combine.

The combining rule is simple. If the left and right subtrees reach the same depth (ld == rd), then deepest nodes live on both sides, so the current node is their common ancestor — return it. If one side goes deeper, the answer must come entirely from that deeper side, so we pass that side's node up unchanged.

Example: with [3,5,1,6,2,0,8,null,null,7,4] the deepest leaves are 7 and 4, both children of node 2. At node 2 the left and right depths tie, so 2 is returned as the LCA.

Because each node is visited exactly once and only does constant work, the whole thing runs in O(n) time.

Time: O(n) Space: O(h)