DSA Tracker

Visualize

Validate Binary Search Tree

Recursive range narrowing (low, high)

time O(n)space O(h) recursion stack

Comparing a node only to its immediate children is the classic trap: it misses violations from further up the tree. Instead carry an open interval (low, high) downward, starting at (-infinity, infinity). A node must strictly fit the interval its ancestors handed down; its left child inherits the same low but a tightened high of the node's own value, and its right child inherits the same high but a tightened low. The moment a node fails its interval, the whole check returns false — no need to look further.

Details

Animated on: root = [5, 1, 4, null, null, 3, 6] — is this a valid BST? Expected answer: false (4 is less than root 5 but sits in 5's right subtree).

Problem:Validate Binary Search TreeMedium

Pattern:Binary Search Tree Problems

Recursive range narrowing (low, high)

step 1 / 8

1
5
?
3
4
6

Call stack

validate(5, -inf, inf)

Enter 5. Its allowed range is (-inf, inf) and 5 fits: continue into its subtrees.

Pseudocode
1FUNCTION validate(node, low, high):
2  IF node = null: RETURN true
3  IF NOT (low < node.val AND node.val < high): RETURN false
4  leftOk <- validate(node.left, low, node.val)
5  rightOk <- validate(node.right, node.val, high)
6  RETURN leftOk AND rightOk
7answer <- validate(root, -infinity, infinity)

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Enter 5. Its allowed range is (-inf, inf) and 5 fits: continue into its subtrees.
  2. Enter 1. Its allowed range is (-inf, 5) and 1 fits: continue into its subtrees.
  3. Back at 1: its left subtree is valid. Now check its right subtree with a tightened lower bound of 1 (still capped at 5).
  4. 1's frame returns true (left true AND right true) and pops off the stack.
  5. Back at 5: its left subtree is valid. Now check its right subtree with a tightened lower bound of 5 (still capped at inf).
  6. Enter 4. Its allowed range is (5, inf) and 4 does NOT fit — an ancestor already forced a tighter bound. This node breaks the BST property.
  7. validate(4, ...) returns false immediately. Its own subtrees are never visited — one violation is enough to fail the whole tree.
  8. 5's frame returns false (left true AND right false) and pops off the stack.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Validate Binary Search Tree in the editorAll BST problemsBack to roadmap