Next Larger Key
MediumTrees
Problem
A ticketing system keeps seat numbers (distinct positive integers) in a binary search tree. Given a seat number key that is in the tree, return the smallest seat number strictly greater than it.
If key is already the largest, return -1. Nodes do not have parent pointers.
Example 1
- Input:
- root = [5, 3, 6, 2, 4, null, null, 1], key = 4
- Output:
- 5
4 has no right subtree, so its successor is the nearest ancestor it lies to the left of: 5.
Example 2
- Input:
- root = [5, 3, 6, 2, 4, null, null, 1], key = 6
- Output:
- -1
Constraints
- 1 ≤ number of nodes ≤ 10^4
- 1 ≤ node.val ≤ 10^6
- key is in the tree; all values are distinct.
Hint
Show the first hint
Without parent pointers, where can the successor be: below key or above it?
Walkthrough
How to approach it
01Clarify before coding
- Is key guaranteed to exist? Yes, though the method works even if it did not.
- Return what when nothing is larger? -1, which cannot collide because values are positive.
- Are there parent pointers? No.
02Brute force
In-order traverse the whole tree and return the value after key.
Cost: O(n) time and O(h) space; it visits the whole tree to answer a question about one path.
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.