Marathon Uphill Endpoints
Binary tree leaf values on strictly increasing root-to-leaf paths, left to right
A marathon organizer stores alternative training routes in a binary tree. Each node is a checkpoint, and its value is the checkpoint's elevation in meters. The root is the starting checkpoint. Following a left or right child continues along that route, and a leaf is a finishing checkpoint.
A route qualifies as strictly uphill if every checkpoint after the root has a strictly greater elevation than the checkpoint immediately before it. A route consisting only of the root qualifies automatically.
Return the elevations of the finishing checkpoints whose complete root-to-leaf routes qualify. List them in left-to-right leaf order: all qualifying leaves in a node's left subtree come before those in its right subtree. Keep repeated elevations when different finishing checkpoints have the same elevation.
If the tree is empty or no route qualifies, return an empty list.
Examples
Example 1
Input: root = [3,5,4,7,2,4,9] Output: [7,9]
The routes with elevations 3 → 5 → 7 and 3 → 4 → 9 qualify, in that left-to-right order. The route through 5 → 2 decreases, and the route through 4 → 4 is not strictly increasing.
Example 2
Input: root = [0,-1,2,null,null,3,3] Output: [3,3]
The route from 0 to -1 does not qualify. Both routes through 0 → 2 → 3 qualify, so the two finishing checkpoints contribute separate entries even though their elevations match.
Constraints
- The tree contains between 0 and 6,000 nodes.
- Each node value is an integer between -1,000,000 and 1,000,000.
- The input tree is represented as a level-order list, with null entries for missing children.
A leaf has no children in the original tree. Pruning a disqualified branch does not turn its parent into a finishing checkpoint. An iterative traversal avoids recursion-depth limits on skewed trees. The intended solution takes O(n) worst-case time and O(h) auxiliary space, excluding the returned list, where h is the tree height.
Hints
Show hint 1Hint 1
A route that contains a non-increasing step cannot become qualifying later.
Show hint 2Hint 2
Visit left children before right children, and append a value only when you reach an original leaf on a qualifying path.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the traversal to allow at most one non-increasing step on each route?
- How would you return the left/right direction string of each qualifying route instead of its finishing elevation?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem