Problem statement

You are given the root of a binary tree with n nodes, whose values are exactly 1 to n (each used once), and an array queries of m values.

Answer each query independently: for queries[i], remove the whole subtree rooted at the node with that value, and report the height of what is left. The tree goes back to its original shape before the next query.

The height of a tree is the number of edges on the longest path from the root down to some node. No query names the root.

Return an array answer where answer[i] is the height after the i-th removal.

Example 1

Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: Removing 4 takes 6, 5 and 7 with it; the longest remaining path is 1 → 3 → 2, two edges.

Example 2

Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: Removing 2 takes 4 and 6 away, so the deepest remaining nodes are at depth 2.

Example 3

Input: root = [1,2], queries = [2]
Output: [0]
Explanation: Only the root is left.

Constraints

• The number of nodes is n, 2 <= n <= 10^5
• 1 <= Node.val <= n, all values are distinct
• m == queries.length
• 1 <= m <= min(n, 10^4)
• 1 <= queries[i] <= n
• queries[i] != root.val

Hints for Height of Binary Tree After Subtree Removal Queries

1. Hint 1

   Recomputing the height per query is O(n) each. Think about what the answer for a node depends on — it is the deepest node outside its subtree.

2. Hint 2

   Walk down from the root carrying rest: the deepest depth reachable without entering the current node's subtree.

3. Hint 3

   Going into the left child, the right subtree becomes available: rest' = max(rest, depth + 1 + height(right)) (with height of an empty tree = -1). Precompute every node's height first.

How to solve Height of Binary Tree After Subtree Removal Queries

After removing the subtree at x, the height is the depth of the deepest node outside that subtree. Walking from the root, the region outside a child's subtree is the region outside its parent's subtree plus the parent itself plus the sibling's subtree — so the answer for every node follows from its parent's answer and its sibling's height.

Approach

1. First pass (post-order): record height[v] for every node (a leaf has height 0, an empty tree -1).
2. Second pass from the root with (node, depth, rest); the root starts with rest = 0.
3. Record answer[node.val] = rest.
4. Recurse into the left child with rest' = max(rest, depth + 1 + height(right)), and into the right child with rest' = max(rest, depth + 1 + height(left)), where a missing sibling contributes depth (the parent alone).
5. Answer each query by looking up answer[queries[i]].

Why it works

The nodes outside a child's subtree are: the nodes outside its parent's subtree (deepest is rest), the parent itself (depth depth), and the sibling's subtree (deepest is depth + 1 + height(sibling), which is depth again when the sibling is missing). Taking the maximum gives the exact height after removing the child's subtree, by induction from the root.

Complexity

• Time — O(n + m)
• Space — O(n)

Pitfalls

• Queries are independent — never actually delete anything.
• A missing sibling still leaves the parent, so it contributes the parent's depth, not depth + 1.
• Height counts edges: a tree of one node has height 0.

Reference solution

Python

from typing import List, Optional

def treeQueries(root: Optional[TreeNode], queries: List[int]) -> List[int]:
    height = {}

    def measure(node):
        if node is None:
            return -1
        h = 1 + max(measure(node.left), measure(node.right))
        height[node.val] = h
        return h

    def h_of(node):
        return -1 if node is None else height[node.val]

    answer = {}

    def fill(node, depth, rest):
        if node is None:
            return
        answer[node.val] = rest
        fill(node.left, depth + 1, max(rest, depth + 1 + h_of(node.right)))
        fill(node.right, depth + 1, max(rest, depth + 1 + h_of(node.left)))

    measure(root)
    fill(root, 0, 0)
    return [answer[q] for q in queries]

Java

public static int[] treeQueries(TreeNode root, int[] queries) {
    int n = countNodes(root);
    int[] height = new int[n + 1], answer = new int[n + 1];
    measure(root, height);
    fill(root, 0, 0, height, answer);
    int[] res = new int[queries.length];
    for (int i = 0; i < queries.length; i++) res[i] = answer[queries[i]];
    return res;
}

static int countNodes(TreeNode node) {
    return node == null ? 0 : 1 + countNodes(node.left) + countNodes(node.right);
}

static int measure(TreeNode node, int[] height) {
    if (node == null) return -1;
    int h = 1 + Math.max(measure(node.left, height), measure(node.right, height));
    height[node.val] = h;
    return h;
}

static void fill(TreeNode node, int depth, int rest, int[] height, int[] answer) {
    if (node == null) return;
    answer[node.val] = rest;
    int hl = node.left == null ? -1 : height[node.left.val];
    int hr = node.right == null ? -1 : height[node.right.val];
    fill(node.left, depth + 1, Math.max(rest, depth + 1 + hr), height, answer);
    fill(node.right, depth + 1, Math.max(rest, depth + 1 + hl), height, answer);
}

C++

vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
    unordered_map<int, int> height, answer;
    function<int(TreeNode*)> measure = [&](TreeNode* node) -> int {
        if (!node) return -1;
        int h = 1 + max(measure(node->left), measure(node->right));
        height[node->val] = h;
        return h;
    };
    auto hOf = [&](TreeNode* node) { return node ? height[node->val] : -1; };
    function<void(TreeNode*, int, int)> fill = [&](TreeNode* node, int depth, int rest) {
        if (!node) return;
        answer[node->val] = rest;
        fill(node->left, depth + 1, max(rest, depth + 1 + hOf(node->right)));
        fill(node->right, depth + 1, max(rest, depth + 1 + hOf(node->left)));
    };
    measure(root);
    fill(root, 0, 0);
    vector<int> res;
    for (int q : queries) res.push_back(answer[q]);
    return res;
}

JavaScript

var treeQueries = function(root, queries) {
    var height = {}, answer = {};
    var measure = function(node) {
        if (node === null) return -1;
        var h = 1 + Math.max(measure(node.left), measure(node.right));
        height[node.val] = h;
        return h;
    };
    var hOf = function(node) { return node === null ? -1 : height[node.val]; };
    var fill = function(node, depth, rest) {
        if (node === null) return;
        answer[node.val] = rest;
        fill(node.left, depth + 1, Math.max(rest, depth + 1 + hOf(node.right)));
        fill(node.right, depth + 1, Math.max(rest, depth + 1 + hOf(node.left)));
    };
    measure(root);
    fill(root, 0, 0);
    return queries.map(function (q) { return answer[q]; });
};

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

More arrays problems

• Maximum Path Sum Between Two Leaves Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard