FunctionRacerProblemsRace

Height Without Each Subtree

HardTreesPython, JavaScript, TypeScript, Java, C++

You are given the root of a binary tree in which all values are different. The height of a tree is the number of links on the longest way from the root down to a leaf.

Each entry of queries is the value of a node other than the root. For each one, imagine cutting off that node together with everything below it, and work out the height of what is left. The queries do not build on each other: every one starts from the full tree.

Return the heights in the order of the queries.

Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.

Example 1

root [5,3,8,1,4,null,9,null,null,null,null,7]
queries [9,8,3,7,1]
returns [2,2,3,2,3]

The full tree has height 3, by the way 5, 8, 9, 7. Cutting 9 or 8 removes that way and leaves height 2. Cutting 3 leaves it alone.

Example 2

root [1,2]
queries [2]
returns [0]

Only the root is left.

Example 3

root [1,null,2,null,3]
queries [3,2]
returns [1,0]

Without 3 the chain is 1, 2. Without 2 only the root stays.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Trees problems