Editorial
Core insight
Height of Binary Tree After Subtree Removal Queries · Tree Traversal Patterns (DFS & BFS)
Core Insight for Height of Binary Tree After Subtree Removal Queries
The key intuition is to realize that the height of the tree is determined by the longest path from the root to a leaf. If we remove a subtree rooted at node u, we break all paths passing through u. The new height of the tree will be determined by the longest path that does not go through u.
Every path from the root to a leaf passes through exactly one node at any specific depth level (up to the path's end). Therefore, if we remove a node u at depth d, the new maximum height is determined by the "cousins" of u—other nodes residing at the same depth d.
Specifically, for any depth level, we only care about the nodes that produce the longest paths.
- Preprocessing: We can compute the
depthof every node and theheightof the subtree rooted at every node. - The Invariant: If we remove node
uat depthdepth[u], the new tree height is the maximum of:- The longest path passing through a different node at the same depth
depth[u]. - The depth of the parent (if no other nodes exist at this depth).
- The longest path passing through a different node at the same depth
By storing the two largest subtree heights for every depth level, we can answer queries instantly. If the node being removed holds the largest height at its level, the answer is the second largest. Otherwise, the answer remains the largest.
Visual Description:
Imagine the recursion tree. As the Postorder Traversal bubbles up from the leaves, each node calculates its height as 1 + max(left_height, right_height). We essentially "annotate" every horizontal level of the tree with the subtree heights found at that level. When a query cuts a branch, we simply look horizontally at that level to see which other branch is longest.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 2458: Height of Binary Tree After Subtree Removal Queries Solution & Explanation
Problem Overview
TL;DR: By precomputing the depth and subtree height of every node using Postorder Traversal, we can determine the new tree height in by checking the two largest subtree heights at the removed node's depth level.
You are provided with the root of a binary tree and a list of independent queries. Each query specifies a node value whose subtree must be temporarily removed. For each query, you must calculate the height of the remaining tree. The tree resets to its original state after every query. This is a popular interview question that tests your ability to optimize tree operations beyond naive simulation.
Brute Force Approach for Height of Binary Tree After Subtree Removal Queries
The naive approach is to simulate the removal process literally for every query.
- For each query node
q: 2. Create a deep copy of the tree (or use a temporary flag to ignore the subtree atq). 3. Traverse the modified tree (using DFS or BFS) to calculate its maximum depth. 4. Store the result. 5. Reset the tree.
1# Pseudo-code for Brute Force
2def solve_naive(root, queries):
3 answers = []
4 for q_val in queries:
5 # 1. Mark node q_val as "removed"
6 # 2. Run DFS from root to find max depth, ignoring "removed" paths
7 current_height = calculate_height(root, ignore=q_val)
8 answers.append(current_height)
9 return answersWhy this fails: The time complexity is , where is the number of queries and is the number of nodes. With constraints up to for both and , this results in roughly operations, which inevitably causes a Time Limit Exceeded (TLE) error. We need a solution that answers each query in time after preprocessing.
Algorithm Strategy: Tree DFS - Recursive Postorder Traversal
-
Data Structures:
depth_map: Stores the depth (distance from root) of each node.height_map: Stores the height (distance to deepest leaf) of the subtree rooted at each node.level_maxes: A hash map (or array) where keys are depths. For each depth, we store the two largest subtree heights found at that depth.
-
Preprocessing (DFS):
- Perform a DFS (Postorder logic).
- For a node
uat depthd:- Recursively calculate heights of left and right children.
height[u] = 1 + max(height[left], height[right]).- Record
depth[u] = d. - Update
level_maxes[d]withheight[u]. Keep only the top 2 distinct values (associated with their node IDs to handle ties correctly).
-
Query Processing:
- For each query node
q:- Retrieve
d = depth_map[q]andh = height_map[q]. - Look at
level_maxes[d]. - If
qis the node responsible for the maximum height at this level, the new tree height isd + second_max_height_at_level. - Otherwise, the new tree height is
d + max_height_at_level.
- Retrieve
- For each query node
Execution Flow
- Initialization: Create maps for depths, heights, and level-wise maximums.
- DFS Traversal (Root, Depth 0):
- If node is null, return -1 (height of null).
- Recursively call DFS for left child with
depth + 1. - Recursively call DFS for right child with
depth + 1. - Current subtree height =
1 + max(left_sub_height, right_sub_height). - Store
depthandheightfor the current node. - Update the "Top 2" list for the current
depth. If the current height is larger than the stored maximums, shift them down.
- Answering Queries:
- Loop through
queries. - Identify the depth
Lof the query node. - Check the precomputed top heights for level
L. - If the query node contributes the absolute longest path at level
L, use the secondary longest path. - Calculate
Result = L + selected_subtree_height. - Append to results.
- Loop through
Proof of Correctness
The height of the binary tree is defined as the maximum number of edges from the root to any leaf. Any path from the root to a leaf can be decomposed into two parts relative to a specific depth : the path from Root to a node at depth (length ), and the path from to a leaf (length ).
The global height is . Since we are removing a subtree at node (where ), we are effectively removing the term from the set of all path lengths. Because all paths reaching depth greater than must pass through some node at depth , the new maximum height must be formed by a path passing through a sibling or cousin of at depth . Therefore, gives the correct new height.
Pattern Reuse Notes
The Tree DFS - Recursive Postorder Traversal pattern used here is fundamental for many tree problems.
- LeetCode 104: Maximum Depth of Binary Tree - Uses the exact same
1 + max(left, right)logic to find height. - LeetCode 110: Balanced Binary Tree - Uses Postorder to calculate heights of both subtrees and immediately check the balance condition.
- LeetCode 124: Binary Tree Maximum Path Sum - Uses Postorder to bubble up the maximum path sum from children to update the global maximum.
- LeetCode 145: Binary Tree Postorder Traversal - The standard implementation of the traversal itself.
By mastering this pattern, you can solve almost any problem requiring "bottom-up" information flow in a tree.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 2458
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <iostream>
5
6using namespace std;
7
8/**
9 * Definition for a binary tree node.
10 * struct TreeNode {
11 * int val;
12 * TreeNode *left;
13 * TreeNode *right;
14 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
15 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
16 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17 * };
18 */
19class Solution {
20 // Map to store the depth of each node: node_val -> depth
21 unordered_map<int, int> depthMap;
22 // Map to store the height of the subtree rooted at each node: node_val -> height
23 unordered_map<int, int> heightMap;
24 // Stores the top 2 largest heights for each depth level
25 // levelMaxes[d] = { {height1, node1}, {height2, node2} }
26 unordered_map<int, vector<pair<int, int>>> levelMaxes;
27
28 int computeHeights(TreeNode* node, int depth) {
29 if (!node) return -1;
30
31 depthMap[node->val] = depth;
32
33 int leftH = computeHeights(node->left, depth + 1);
34 int rightH = computeHeights(node->right, depth + 1);
35
36 int currentH = 1 + max(leftH, rightH);
37 heightMap[node->val] = currentH;
38
39 // Update top 2 heights for this depth
40 auto& top2 = levelMaxes[depth];
41 top2.push_back({currentH, node->val});
42 sort(top2.rbegin(), top2.rend()); // Sort descending
43 if (top2.size() > 2) {
44 top2.pop_back(); // Keep only top 2
45 }
46
47 return currentH;
48 }
49
50public:
51 vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
52 depthMap.clear();
53 heightMap.clear();
54 levelMaxes.clear();
55
56 // 1. Precompute depths and subtree heights using Postorder DFS
57 computeHeights(root, 0);
58
59 vector<int> answer;
60 answer.reserve(queries.size());
61
62 // 2. Answer queries in O(1)
63 for (int q : queries) {
64 int d = depthMap[q];
65 int h = heightMap[q];
66
67 // Retrieve top heights at this depth
68 auto& tops = levelMaxes[d];
69
70 // If the node being removed is the one with the largest height at this level
71 if (tops[0].second == q) {
72 if (tops.size() == 2) {
73 // Use the second largest height
74 answer.push_back(d + tops[1].first);
75 } else {
76 // No other node at this depth extends further; max path ends at level d-1
77 answer.push_back(d - 1);
78 }
79 } else {
80 // The node removed is not the largest, so global max remains unchanged
81 answer.push_back(d + tops[0].first);
82 }
83 }
84
85 return answer;
86 }
87};Java Solution for LeetCode 2458
1import java.util.*;
2
3/**
4 * Definition for a binary tree node.
5 * public class TreeNode {
6 * int val;
7 * TreeNode left;
8 * TreeNode right;
9 * TreeNode() {}
10 * TreeNode(int val) { this.val = val; }
11 * TreeNode(int val, TreeNode left, TreeNode right) {
12 * this.val = val;
13 * this.left = left;
14 * this.right = right;
15 * }
16 * }
17 */
18class Solution {
19 // node val -> depth
20 private Map<Integer, Integer> depthMap = new HashMap<>();
21 // node val -> subtree height
22 private Map<Integer, Integer> heightMap = new HashMap<>();
23 // depth -> list of top 2 pairs (height, nodeVal)
24 private Map<Integer, List<int[]>> levelMaxes = new HashMap<>();
25
26 public int[] treeQueries(TreeNode root, int[] queries) {
27 // 1. Precompute depths and heights
28 computeHeights(root, 0);
29
30 int[] answer = new int[queries.length];
31
32 // 2. Process queries
33 for (int i = 0; i < queries.length; i++) {
34 int q = queries[i];
35 int d = depthMap.get(q);
36
37 List<int[]> tops = levelMaxes.get(d);
38
39 // Check if the removed node holds the max height at this level
40 if (tops.get(0)[1] == q) {
41 if (tops.size() > 1) {
42 answer[i] = d + tops.get(1)[0];
43 } else {
44 // No cousins, path stops at parent
45 answer[i] = d - 1;
46 }
47 } else {
48 // Max height is determined by a different node
49 answer[i] = d + tops.get(0)[0];
50 }
51 }
52
53 return answer;
54 }
55
56 private int computeHeights(TreeNode node, int depth) {
57 if (node == null) return -1;
58
59 depthMap.put(node.val, depth);
60
61 int leftH = computeHeights(node.left, depth + 1);
62 int rightH = computeHeights(node.right, depth + 1);
63
64 int currentH = 1 + Math.max(leftH, rightH);
65 heightMap.put(node.val, currentH);
66
67 // Manage top 2 heights for this level
68 levelMaxes.putIfAbsent(depth, new ArrayList<>());
69 List<int[]> tops = levelMaxes.get(depth);
70
71 tops.add(new int[]{currentH, node.val});
72 // Sort descending by height
73 tops.sort((a, b) -> b[0] - a[0]);
74
75 if (tops.size() > 2) {
76 tops.remove(2);
77 }
78
79 return currentH;
80 }
81}Python Solution for LeetCode 2458
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7
8class Solution:
9 def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
10 depth_map = {}
11 height_map = {}
12 # Stores top 2 heights at each level: depth -> [(height, node_val), ...]
13 level_maxes = collections.defaultdict(list)
14
15 def compute_heights(node, depth):
16 if not node:
17 return -1
18
19 depth_map[node.val] = depth
20
21 left_h = compute_heights(node.left, depth + 1)
22 right_h = compute_heights(node.right, depth + 1)
23
24 current_h = 1 + max(left_h, right_h)
25 height_map[node.val] = current_h
26
27 # Update top 2 for this level
28 level_maxes[depth].append((current_h, node.val))
29 level_maxes[depth].sort(key=lambda x: x[0], reverse=True)
30 if len(level_maxes[depth]) > 2:
31 level_maxes[depth].pop()
32
33 return current_h
34
35 # 1. Precompute
36 compute_heights(root, 0)
37
38 answers = []
39
40 # 2. Answer queries
41 for q in queries:
42 d = depth_map[q]
43 tops = level_maxes[d]
44
45 # If q is the node with the largest height at this level
46 if tops[0][1] == q:
47 if len(tops) > 1:
48 answers.append(d + tops[1][0])
49 else:
50 answers.append(d - 1)
51 else:
52 answers.append(d + tops[0][0])
53
54 return answers