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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Validate Binary Search Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →