Height After Pruning
HardTrees
Problem
You are given the root of a binary tree with n nodes whose values are the distinct integers 1..n, and an array queries. For each query value q (never the root), imagine cutting off the whole subtree rooted at the node with value q, and report the height of what remains. Each query is independent: the tree is restored before the next one.
Height is counted in nodes (a lone root has height 1). Return the answers in query order.
Example 1
- Input:
- root = [5, 8, 9, 2, 1, 3, 7, 4, 6], queries = [3, 2, 4, 8]
- Output:
- [4, 3, 4, 3]
Cutting 2 removes 2, 4 and 6; the deepest remaining paths are 5 → 8 → 1 and 5 → 9 → 3, three nodes each.
Example 2
- Input:
- root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7], queries = [4]
- Output:
- [3]
Without 4's subtree the longest path is 1 → 3 → 2.
Constraints
- 2 ≤ n ≤ 10^5
- Values are a permutation of 1..n
- 1 ≤ queries.length ≤ 10^4
- Each query is a value of a non-root node
Hint
Show the first hint
Re-measuring the height for every query costs O(n) each. What does the answer for node q depend on?
Walkthrough
How to approach it
01Clarify before coding
- Are queries independent? Yes, each starts from the full tree.
- Can a query be the root? No, so something always remains.
- Height in nodes? Yes: depth of the root is 1.
02Brute force
For each query, run a height computation that treats node q as missing.
Cost: O(n · m): 10^5 nodes × 10^4 queries = 10^9 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.