Skip to main content

67. Validate Binary Search Tree

mediumAsked at Reddit

Determine whether a binary tree is a valid BST. Reddit uses this to test the bounded-recursion pattern — the same shape used when validating that a comment-tree's parent timestamps satisfy a strict-monotonic constraint.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site favorite.
  • Blind (2025-11)— Reported in Reddit comments-team rounds.

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: 4's left child 3 is less than 5 (root), violates BST.

Approaches

1. Compare each node to children only

At each node, check node.val > left.val and < right.val.

Time
O(n)
Space
O(h)
// WRONG: doesn't validate against grandparents.
// [5,1,4,null,null,3,6] — at node 4 we compare to 3 (left) and 6 (right), but we missed that 3 < 5 (root).

Tradeoff: Local check misses transitive constraints.

2. Recurse with min/max bounds (optimal)

Each recursion carries the valid range. Left child has (min, node.val); right has (node.val, max).

Time
O(n)
Space
O(h)
function isValidBST(root) {
  function valid(node, min, max) {
    if (!node) return true;
    if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) return false;
    return valid(node.left, min, node.val) && valid(node.right, node.val, max);
  }
  return valid(root, null, null);
}

Tradeoff: O(n) time. Bounds carry transitive constraints up the recursion.

Reddit-specific tips

Reddit interviewers grade on whether you avoid the local-compare trap. Bonus signal: alternative inorder traversal — values must be strictly increasing. Demonstrate both methods if time permits.

Common mistakes

  • Only comparing to immediate children (misses grand-parent constraint).
  • Using <= instead of <, missing the 'strictly' BST rule.
  • Using -Infinity / Infinity but missing edge case (Node.val can equal them in some variants).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • BST iterator (LC 173).
  • Recover BST (LC 99) — two nodes swapped.
  • Convert sorted array to BST (LC 108).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Inorder traversal alternative?

An inorder traversal of a BST must be strictly increasing. Walk inorder; check each value > prev.

Why null instead of Infinity?

Node.val could be 2^31 - 1 which equals Number.MAX_SAFE_INTEGER. Using null avoids accidental equality.

Practice these live with InterviewChamp.AI

Drill Validate Binary Search Tree and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →