#2458

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Height of Binary Tree After Subtree Removal Queries

Compute the height of a binary tree efficiently after removing subtrees, using traversal and precomputed node state tracking.

array tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree with n uniquely valued nodes from 1 to n, and an array queries of size m. For each query, you need to calculate the tree's height after removing the entire subtree rooted at the specified node.

Return an array answer of size m where answer[i] represents the height of the tree after the ith subtree removal query. Each query is independent, and the root node will never be removed.

Examples

Example 1

Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]

Output: [2]

The diagram above shows the tree after removing the subtree rooted at node with value 4. The height of the tree is 2 (The path 1 -> 3 -> 2).

Example 2

Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]

Output: [3,2,3,2]

We have the following queries:

Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).

Constraints

The number of nodes in the tree is n.
2 <= n <= 105
1 <= Node.val <= n
All the values in the tree are unique.
m == queries.length
1 <= m <= min(n, 104)
1 <= queries[i] <= n
queries[i] != root.val

Solution Approach

Precompute Depths and Heights

Perform a DFS traversal to compute the depth of each node and the height of the subtree rooted at each node. Store the maximum heights for each level to handle removals efficiently.

Track Maximum Heights Per Level

For each depth level, keep track of the two highest subtree heights. When a node is removed, the new height at that level can be derived from the remaining highest height, avoiding repeated traversal.

Answer Queries in O(1) Time

After precomputing the depth and maximum heights, each query simply looks up the affected level and returns the precomputed new height. This ensures all m queries are answered efficiently without re-traversing the tree.

Complexity Analysis

Metric	Value
Time	O(n + q)
Space	O(n)

DFS traversal visits all n nodes once, taking O(n) time and O(n) space for storing depths and heights. Each of the m queries is answered in O(1), resulting in total O(n + m) time and O(n) space.

What Interviewers Usually Probe

Candidate considers preprocessing depths and heights to avoid repeated computation per query.
Candidate identifies that tracking two maximum heights per level allows O(1) query resolution.
Candidate correctly handles edge cases such as removing nodes at maximum depth affecting tree height.

Common Pitfalls or Variants

Common pitfalls

Recomputing tree height from scratch for each query, causing TLE for large n.
Failing to account for the second largest height at a depth, returning wrong height when the largest node is removed.
Incorrectly assuming subtree removal affects parent levels without adjusting maximums properly.

Follow-up variants

Compute remaining subtree sizes instead of heights after removal queries.
Answer subtree sum queries after removals using a similar traversal and precomputation.
Handle dynamic insertion and deletion with height updates using segment tree analogs.

FAQ

What is the primary pattern used in Height of Binary Tree After Subtree Removal Queries?

The main pattern is binary-tree traversal and state tracking to precompute the effect of subtree removals on tree height.

Can each query be answered without traversing the entire tree?

Yes, by precomputing the depth and height for each node and tracking level maxima, each query can be answered in O(1) time.

How do I handle removing the node with the current maximum depth?

Keep track of the two tallest subtree heights per depth level so when the tallest is removed, the second tallest determines the new height.

What is the time complexity for n nodes and m queries?

The total time complexity is O(n + m), with O(n) for DFS precomputation and O(1) per query.

Does this method work if the root node is removed?

No, the problem guarantees the root node is never removed; the solution relies on the root remaining to calculate heights correctly.

terminal

Solution

Solution 1: Two DFS Traversals

First, we perform a DFS traversal to determine the depth of each node, which we store in a hash table $d$, where $d[x]$ represents the depth of node $x$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

# 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 treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
        def f(root):
            if root is None:
                return 0
            l, r = f(root.left), f(root.right)
            d[root] = 1 + max(l, r)
            return d[root]

        def dfs(root, depth, rest):
            if root is None:
                return
            depth += 1
            res[root.val] = rest
            dfs(root.left, depth, max(rest, depth + d[root.right]))
            dfs(root.right, depth, max(rest, depth + d[root.left]))

        d = defaultdict(int)
        f(root)
        res = [0] * (len(d) + 1)
        dfs(root, -1, 0)
        return [res[v] for v in queries]

Solution 2: One DFS + Sorting

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

# 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 treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
        def f(root):
            if root is None:
                return 0
            l, r = f(root.left), f(root.right)
            d[root] = 1 + max(l, r)
            return d[root]

        def dfs(root, depth, rest):
            if root is None:
                return
            depth += 1
            res[root.val] = rest
            dfs(root.left, depth, max(rest, depth + d[root.right]))
            dfs(root.right, depth, max(rest, depth + d[root.left]))

        d = defaultdict(int)
        f(root)
        res = [0] * (len(d) + 1)
        dfs(root, -1, 0)
        return [res[v] for v in queries]

Continue Practicing

#2467 most profitable path in a tree #2476 closest nodes queries in a binary search tree #2385 amount of time for binary tree to be infected