Library Index Audit
A library's search kiosk finds books with a binary search tree of shelf numbers. At each shelf number the kiosk goes left to look for smaller numbers and right to look for larger ones, so it can skip a whole branch at every step. That only works if the tree is laid out correctly.
Over the summer, volunteers edited the tree by hand. Before the kiosk goes back online, the head librarian wants an audit: is every shelf number still in a place where the kiosk will find it?
Your task
Write indexIsValid(root). Return true if the tree is a valid binary search tree, and false otherwise. In a valid tree, for every node, every value in its left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly larger. Equal values anywhere make it invalid.
An empty tree is valid. Trees are shown in level order, like [50, 30, 70, 20, 40], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
indexIsValid(root: TreeNode) → bool
Examples
root = [50, 30, 70, 20, 40, 60, 80]
true
Everything under 30 (20 and 40) is below 50, everything under 70 (60 and 80) is above 50, and each small family is in order too. A search for 60 goes right at 50, left at 70, and finds it.
root = [50, 30, 70, 20, 55, 60, 80]
false
55 is the right child of 30, and 55 > 30, so that pair looks fine. But 55 sits in the left subtree of 50, where every number must be below 50. A search for 55 would go right at 50 and never find it.
Constraints
- 0 ≤ number of shelf numbers ≤ 1,000
- -2,147,483,648 ≤ shelf number ≤ 2,147,483,647
- The tree is at most 500 levels deep.
Start with brute force
For each node, scan its entire left subtree to confirm everything is smaller, and its entire right subtree to confirm everything is larger.
That is correct, but a node near the top scans almost the whole tree, and a long chain of 1,000 nodes makes it about 500,000 comparisons, which is O(n²). The repeated work is checking the same deep nodes against every ancestor separately. Carrying the tightest limits down the tree checks each node once.
Hints
0 of 4 shown- Hint 1
In the second example, every parent and child pair looks correct on its own. Which ancestor does 55 disagree with?
- Hint 2
Comparing a node with its parent is not enough. Each node has a range of allowed values, set by all of its ancestors. What is the allowed range for the node where 55 sits?
- Hint 3
When you step left from a node with value v, the upper limit becomes v. When you step right, the lower limit becomes v. The other limit is inherited unchanged.
- Hint 4
Recurse with
(node, low, high), starting with no limits. A null node is valid. A node is invalid ifval <= loworval >= high. Otherwise check the left child with(low, val)and the right child with(val, high). Use null (or infinity) for "no limit", not the smallest or largest shelf number, because those numbers can appear in the tree.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every node lives inside a window of allowed values. The root's window is open on both sides. Going left closes the window from above at the parent's value; going right closes it from below.
Trace [50, 30, 70, 20, 55, 60, 80]:
- 50: window (none, none). Fine. Left child gets (none, 50), right child gets (50, none).
- 30: window (none, 50). Fine. Its left child gets (none, 30), its right child gets (30, 50).
- 20: window (none, 30). Fine.
- 55: window (30, 50). 55 ≥ 50, so return false.
The window at 55 remembers both 30 (its parent) and 50 (its grandparent). That is exactly the information a parent-only check throws away.
function indexIsValid(root) {
// low and high are exclusive limits; null means no limit.
function check(node, low, high) {
if (node === null) return true;
if (low !== null && node.val <= low) return false;
if (high !== null && node.val >= high) return false;
return check(node.left, low, node.val) // left: new upper limit
&& check(node.right, node.val, high); // right: new lower limit
}
return check(root, null, null);
}def index_is_valid(root):
# low and high are exclusive limits; None means no limit.
def check(node, low, high):
if node is None:
return True
if low is not None and node.val <= low:
return False
if high is not None and node.val >= high:
return False
return (check(node.left, low, node.val) # left: new upper limit
and check(node.right, node.val, high)) # right: new lower limit
return check(root, None, None)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.