Skip to main content

69. Validate Binary Search Tree

mediumAsked at Plaid

Determine if a binary tree is a valid BST. Plaid asks this because validating that a freshly-built merchant-category tree obeys its strict-ordering invariant is the same primitive — bugs in the invariant cause cascading mis-classification later.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II onsite — framed as category-tree invariant check.
  • Blind (2026)— Plaid backend OA.

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as: 1) The left subtree of a node contains only nodes with keys less than the node's key. 2) The right subtree of a node contains only nodes with keys greater than the node's key. 3) 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. Check immediate children only

Verify each node is greater than its left child and less than its right child.

Time
O(n)
Space
O(h)
// WRONG — doesn't catch the case where a left descendant is > root.

Tradeoff: Doesn't work. A node could violate ordering with a grandchild.

2. Recurse with min/max bounds

Each node must lie strictly between its inherited min and max bounds. Recurse with updated bounds for each child.

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

Tradeoff: Bounds propagate the BST invariant down. Use -Infinity/Infinity as initial bounds to avoid overflow on int boundaries.

Plaid-specific tips

Plaid grades this on whether you propagate bounds rather than only check parent. Bonus signal: explicitly call out the trap — checking only immediate children misses [5, 1, 4, null, null, 3, 6] where 3 < 5 violates BST despite 4 having valid local children. Connect to category-tree invariant: 'every descendant of a category must fall within the category's id range.'

Common mistakes

  • Checking only direct children — fails on transitive violations.
  • Using <= instead of < (or >= instead of >) — depends on whether duplicates are allowed.
  • Initializing bounds to int min/max instead of -Infinity/Infinity — fails on boundary values.

Follow-up questions

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

  • Inorder traversal sortedness check — alternative O(n) approach.
  • Recover a corrupted BST where two nodes are swapped (LC 99).
  • Count valid BSTs in a tree.

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, not just inorder?

Both work. Bounds propagation is more explicit about the invariant; inorder check is shorter. Plaid asks for the bounds version because it teaches the invariant clearly.

Why -Infinity instead of Number.MIN_SAFE_INTEGER?

Node values can legally be MIN_SAFE_INTEGER. Using a value within the int range as a sentinel risks false negatives.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →