Skip to main content

98. Validate Binary Search Tree

medium

Confirm a binary tree satisfies the BST property: every node's value strictly larger than all in its left subtree and strictly smaller than all in its right subtree. Easy to write a subtly wrong solve — the right framing uses min/max bounds.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: the left subtree of a node contains only nodes with keys less than the node's key; the right subtree of a node contains only nodes with keys greater than the node's key; both the left and right subtrees must also be binary search trees.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

Examples

Example 1

Input
root = [2,1,3]
Output
true

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false

Explanation: The root node's value is 5 but its right child's value is 4.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Checking only that node.left.val < node.val < node.right.val at each node is WRONG — it misses violations deeper in subtrees.

Hint 2

Each node has a valid value range [min, max] determined by its ancestors. Pass those bounds down.

Hint 3

Alternative: in-order traversal of a BST yields strictly-increasing values. Validate by checking each value > prev.

Solution approach

Reveal approach

Pass min/max bounds through recursion. Helper function isValid(node, min, max): if node is null return true; if node.val <= min or node.val >= max return false; return isValid(node.left, min, node.val) AND isValid(node.right, node.val, max). Initial call: isValid(root, -Infinity, +Infinity). The bounds tighten as you descend, so violations anywhere in a subtree are caught. O(n) time, O(h) recursion space. Alternative: in-order traversal — visit nodes left-root-right and verify strictly-increasing values.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • recursion
  • bst

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

More Trees practice problems

See all Trees problems →