Validate Binary Search Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Check that a binary tree is a valid binary search tree: every node is bigger than everything in its left subtree and smaller than everything in its right subtree.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1For the tree [5, 1, 4, null, null, 3, 6], is 3 in a valid place? It is bigger than its parent 4... no, smaller. Which ancestor does it break?
- Hint 2Each node must lie strictly between a lower and an upper limit, and the limits tighten as you go down.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A multi-storey building where each room has an allowed age range for its occupant. The ground-floor door says "any age". Going into the left wing the upper limit becomes the age of the person in the room you just left; going into the right wing the lower limit becomes that age. A grandchild room carries the limits of every ancestor, not just its parent, which is exactly the mistake people make.
- The obvious way
For every node compare it with every node of its subtrees: O(n²).
- The key insight
Carry a pair (low, high) down the recursion. The root may be anything. For the left child, the new high is the parent's value; for the right child, the new low is the parent's value. A node outside its (low, high) range makes the tree invalid. Each node is checked once.
- The algorithm
- Start at the root with the range (nothing below, nothing above).
- Node outside (low, high)? Answer False. Empty spot? True.
- Check the left child with (low, this value).
- Check the right child with (this value, high). Both must be True.
Watch it run
Exampletree = [5, 1, 4, null, null, 3, 6]
Root 5: allowed range is anything. Fine. Left child must be below 5, right child above 5.
5 ok
Where people slip
- Do not compare only with the parent: [5, 4, 6, null, null, 3, 7] looks fine locally but 3 sits in the right subtree of 5.
- Use limits wider than int (long) so a node equal to the int limit is handled.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_valid_bst(root):
def check(node, low, high):
if node is None:
return True
if not (low < node.val < high): # outside the range from the ancestors
return False
return check(node.left, low, node.val) and check(node.right, node.val, high)
return check(root, float("-inf"), float("inf"))Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.