LeetCode 98 · Medium · Trees

Validate Binary Search Tree

Decide whether a binary tree is a valid binary search tree: every value in a node's left subtree is smaller than the node, every value in its right subtree is bigger, and both subtrees follow the same rule.

O(n)time
O(h)space · call stack
DFSpass (low, high) bounds down

level order as on LeetCode, null = no child · 1 to 15 nodes, 4 levels · values −99 to 99

Call stack one frame per valid(node, left, right) call · labels under the nodes = their (left, right) bounds · badges = returned ✓ / ✗

public boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean valid(TreeNode node, long left, long right) { if (node == null) { return true; } if (!(left < node.val && node.val < right)) { return false; } return valid(node.left, left, node.val) && valid(node.right, node.val, right);}
node
—
left
—
right
—
check
—
return
—

Why it works

  1. Brute force checks each node against its whole subtrees: the max of the left must be smaller, the min of the right bigger. Recomputing those for every node costs O(n²) on a chain.
  2. Every node lives inside an open interval set by its ancestors. Going left, the parent's value becomes the new upper bound; going right, it becomes the new lower bound. A node is fine exactly when left < val < right, and those checks together are the whole BST rule.
  3. One O(1) check per node: O(n) time. The bounds ride in the call frames: O(h) space. The first failure stops the search through &&.
  4. Pitfall: comparing a node only with its parent. In the "inherited bound" preset, 3 is a correct left child of 6, but it sits in the right subtree of 5, where every value must exceed 5. The inherited lower bound 5 catches it. Use long bounds: with int bounds, a node holding Integer.MIN_VALUE or Integer.MAX_VALUE would be rejected wrongly.
  5. Alternative: an in-order traversal of a BST is strictly increasing, so walk in-order and compare each value with the previous one. Duplicates fail both checks, as they should.