Height After Cutting a Branch
HardTrees
Problem
A binary tree has n nodes with distinct values. For each value in queries, imagine cutting off the whole subtree rooted at that node (the node and all its descendants) and report the height of what remains, measured in edges from the root to the deepest remaining node.
Each query is independent: the tree is restored before the next one. No query names the root. Return the answers in query order.
Example 1
- Input:
- root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7], queries = [4]
- Output:
- [2]
Removing 4 also removes 6, 5 and 7; the deepest remaining path is 1 → 3 → 2 (2 edges).
Example 2
- Input:
- root = [5, 8, 9, 2, 1, 3, 7, 4, 6], queries = [3, 2, 4, 8]
- Output:
- [3, 2, 3, 2]
Constraints
- 2 ≤ n ≤ 10^5
- 1 ≤ queries.length ≤ 10^4
- Every query is a value in the tree other than the root's.
Hint
Show the first hint
Recomputing the height per query costs O(n) each. What do the nodes that survive a cut have in common in some traversal order?
Walkthrough
How to approach it
01Clarify before coding
- Height in edges or nodes? Edges: a lone root has height 0.
- Are queries independent? Yes, every query starts from the original tree.
- Can a query be the root? No, so something always remains.
02Brute force
For each query, run a DFS that skips the cut subtree and measures the deepest remaining node.
Cost: O(n·q) time: 10^9 operations for n = 10^5 and q = 10^4.
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.