Validate Binary Search Tree

Medium#98in-order

You get the root of a binary tree. Say whether it is a binary search tree: at every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. Our tree: 10 with children 5 and 15; 15 has children 6 and 20 — the answer is false: 6 is in the right subtree of 10 but smaller than 10.

98 Validate Binary Search TreeWalkthrough · 1×

Example: check that a binary tree is a binary search tree: walk it in order and make sure every value is larger than the one before.

nonenonenonenonenonenone10515620in order—call stacktop on the right—
not visitedwaiting on the call stackcurrent callprev, compared with the nodein order so far, ↑ what it returnednone: an empty child

prev = none: no value seen yet

01/29
restart · back · play · step
Speed
1function isValidBST(root):
2 prev = none // shared by every call of inorder
3 return inorder(root)
4
5function inorder(node):
6 if node is none:
7 return true
8 if not inorder(node.left):
9 return false
10 if prev is not none and node.val <= prev:
11 return false
12 prev = node.val
13 return inorder(node.right)
state
node
–
prev
–
click a step to go back

← → step · space play/pause

Why it works

  1. A tree is a BST exactly when its in-order values go strictly up, so it is enough to compare each value with prev, the one right before it.
  2. Comparing a node with its children is not enough: 6 < 15 is fine for a left child, yet 6 sits right of 10. In order, 6 comes straight after 10, and that is where it fails.
  3. The first false goes straight back up through every call, so the rest of the tree is never visited.

Complexity

Time O(n): each node is visited at most once. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.