Smallest Subtree with all the Deepest Nodes

Medium
1932.

Smallest Subtree with all the Deepest Nodes

Smallest Subtree with all the Deepest Nodes is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google and Meta interviews.

Given the root of a binary tree with distinct values, the deepest nodes are those at the greatest distance from the root.

Return the smallest subtree that contains all of the deepest nodes — that is, the subtree rooted at their lowest common ancestor. The subtree of a node is the node plus all of its descendants; return it as that subtree's level order.

Example 1

Input
root = [3,5,1,6,2,0,8,null,null,7,4]
Output
[2,7,4]
Explanation
The deepest nodes are 7 and 4; the smallest subtree holding both is the one rooted at their parent 2.

Example 2

Input
root = [1]
Output
[1]
Explanation
The root is the only, and so the deepest, node.

Example 3

Input
root = [0,1,3,null,2]
Output
[2]
Explanation
2 is the single deepest node, and the smallest subtree containing it is 2 alone.

Constraints

  • The number of nodes in the tree is in the range [1, 500]
  • 0 <= Node.val <= 500
  • The values of the nodes in the tree are unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var subtreeWithAllDeepest = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Subtree with all the Deepest Nodes — Solution

Smallest Subtree with all the Deepest Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest Subtree with all the Deepest Nodes is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google and Meta interviews.

Problem statement

Given the root of a binary tree with distinct values, the deepest nodes are those at the greatest distance from the root.

Return the smallest subtree that contains all of the deepest nodes — that is, the subtree rooted at their lowest common ancestor. The subtree of a node is the node plus all of its descendants; return it as that subtree's level order.

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: The deepest nodes are 7 and 4; the smallest subtree holding both is the one rooted at their parent 2.

Example 2

Input: root = [1]
Output: [1]
Explanation: The root is the only, and so the deepest, node.

Example 3

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: 2 is the single deepest node, and the smallest subtree containing it is 2 alone.

Constraints

  • The number of nodes in the tree is in the range [1, 500]
  • 0 <= Node.val <= 500
  • The values of the nodes in the tree are unique

Hints for Smallest Subtree with all the Deepest Nodes

  1. Hint 1

    If the left subtree is deeper than the right one, every deepest node is on the left — the answer is inside the left subtree.

  2. Hint 2

    If both subtrees have the same depth, the deepest nodes are split between them (or the node is a leaf), so the node itself is the answer.

  3. Hint 3

    One post-order DFS can return two things per node: its subtree's depth and the answer for that subtree.

How to solve Smallest Subtree with all the Deepest Nodes

Compare the depths of the two subtrees at every node. The deeper side holds all the deepest nodes, so its answer carries up unchanged; when the depths tie, the deepest nodes lie on both sides and the current node is their lowest common ancestor.

Approach

  1. deep(node) returns (depth, answer); for null it is (0, null).
  2. Compute (dl, l) = deep(left) and (dr, r) = deep(right).
  3. If dl > dr, return (dl + 1, l); if dr > dl, return (dr + 1, r).
  4. If they are equal, return (dl + 1, node). The answer is the second part of deep(root).

Why it works

By induction, deep returns the height of a subtree and the lowest node containing all of that subtree's deepest nodes. If one side is strictly deeper, the subtree's deepest nodes all lie in it, so its answer is correct here too; if the sides tie, deepest nodes occur on both sides (or the node is a leaf), and the only node containing both groups is the node itself.

Complexity

  • Time — O(n) — each node is visited once
  • Space — O(h) for the recursion

Pitfalls

  • Computing heights separately at every node makes it O(n^2) on a chain; return depth and answer together.
  • A single deepest node is its own answer — the subtree is just that node (with its descendants, of which it has none).

Reference solution

Python

from typing import Optional

def subtreeWithAllDeepest(root: Optional[TreeNode]) -> Optional[TreeNode]:
    def deep(node):
        if node is None:
            return 0, None
        dl, l = deep(node.left)
        dr, r = deep(node.right)
        if dl > dr:
            return dl + 1, l
        if dr > dl:
            return dr + 1, r
        return dl + 1, node
    return deep(root)[1]

Java

public static TreeNode subtreeWithAllDeepest(TreeNode root) {
    return deepest(root, new int[1]);
}

// Returns the answer for the subtree and stores its depth in depth[0].
static TreeNode deepest(TreeNode node, int[] depth) {
    if (node == null) { depth[0] = 0; return null; }
    int[] a = new int[1], b = new int[1];
    TreeNode l = deepest(node.left, a), r = deepest(node.right, b);
    if (a[0] > b[0]) { depth[0] = a[0] + 1; return l; }
    if (b[0] > a[0]) { depth[0] = b[0] + 1; return r; }
    depth[0] = a[0] + 1;
    return node;
}

C++

pair<int, TreeNode*> deepest(TreeNode* node);

TreeNode* subtreeWithAllDeepest(TreeNode* root) {
    return deepest(root).second;
}

pair<int, TreeNode*> deepest(TreeNode* node) {
    if (!node) return {0, nullptr};
    auto a = deepest(node->left), b = deepest(node->right);
    if (a.first > b.first) return {a.first + 1, a.second};
    if (b.first > a.first) return {b.first + 1, b.second};
    return {a.first + 1, node};
}

JavaScript

var subtreeWithAllDeepest = function(root) {
    return deepest(root)[1];
};

var deepest = function(node) {
    if (node === null) return [0, null];
    var a = deepest(node.left), b = deepest(node.right);
    if (a[0] > b[0]) return [a[0] + 1, a[1]];
    if (b[0] > a[0]) return [b[0] + 1, b[1]];
    return [a[0] + 1, node];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)