Skip to main content

73. Validate Binary Search Tree

mediumAsked at Snowflake

Determine whether a tree is a valid BST. Snowflake asks this to test the global-constraint vs local-check distinction — same shape as validating cross-table constraints during schema changes.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake compiler-team uses this in onsites to set up constraint-validation follow-up.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake new-grad screens.

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

Approaches

1. Local check (broken)

At each node, check left < node < right. Easy to write, wrong for non-trivial trees.

Time
O(n)
Space
O(h)
// outline: only check immediate children. Fails on [5, 1, 4, null, null, 3, 6] — 3 is to the right of 5 even though it's <.
// Mention only to reject.

Tradeoff: Fails because BST is a GLOBAL constraint, not local.

2. Recurse with min/max bounds (optimal)

Helper validate(node, lo, hi). At each node, val must be in (lo, hi). Recurse left with hi = val, right with lo = val.

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

Tradeoff: Propagates bounds top-down. Single pass, O(h) stack.

Snowflake-specific tips

Snowflake interviewers grade this on whether you spot that BST is a GLOBAL constraint — locally checking children isn't enough. Bonus signal: pivot to in-order traversal returning a sorted sequence as an alternative proof, and discuss when each version is preferred.

Common mistakes

  • Doing only local left < node < right check — fails subtle cases like [5, 1, 4, null, null, 3, 6].
  • Using <= or >= instead of < and > — BSTs have strict ordering.
  • Passing values instead of references for bounds — works in JS, but make sure the propagation is clear.

Follow-up questions

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

  • Recover BST (LC 99) — fix the swapped nodes.
  • Inorder traversal validation.
  • How does Snowflake validate cross-table constraints?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why bounds propagation?

A BST's left subtree must be < node, AND that node's left ancestor's bound must also apply to the left subtree. Passing bounds down enforces both.

What about the in-order approach?

An in-order traversal of a valid BST yields strictly ascending values. Compare each value to the previous — single pass, O(h) space for the stack.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →