#2458
Height of Binary Tree After Subtree Removal Queries
HardArrayTreeDepth-First SearchBreadth-First SearchBinary TreeHash MapTree Traversal
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Instead of recalculating the height for each query, we can precompute the heights of all subtrees in a single traversal. This allows us to answer each query in constant time.
⚙️
Algorithm
2 steps- 1Step 1: Perform a DFS to calculate the height of each subtree and store it in a dictionary.
- 2Step 2: For each query, simply retrieve the precomputed height of the tree after removing the specified subtree.
solution.py24 lines
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def __init__(self):
9 self.height_map = {}
10
11 def calculateHeights(self, root):
12 if not root:
13 return -1
14 left_height = self.calculateHeights(root.left)
15 right_height = self.calculateHeights(root.right)
16 self.height_map[root.val] = 1 + max(left_height, right_height)
17 return self.height_map[root.val]
18
19 def treeQueries(self, root, queries):
20 self.calculateHeights(root)
21 results = []
22 for query in queries:
23 results.append(self.height_map[root.val] - self.height_map[query])
24 return resultsℹ
Complexity note: The complexity is O(n) because we traverse the tree once to compute heights, and each query is answered in O(1) using the precomputed heights.
- 1Precomputing results can drastically reduce query time.
- 2Understanding tree heights is crucial for efficient solutions.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.