Skip to main content

61. Validate Binary Search Tree

mediumAsked at Workday

Determine if a binary tree is a valid BST. Workday uses this to test recursion with bounds — same pattern as validating an org-chart's pay-grade ordering: every manager outranks all reports.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — tree canonical.
  • Blind (2025)— Workday compensation team — direct pay-grade analogy.

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST has: the left subtree of a node contains only nodes with keys less than the node's key; the right subtree only with keys greater; both 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.

Approaches

1. Naive: check only direct children

At each node, ensure left.val < node.val < right.val.

Time
O(n)
Space
O(h)
// fails on [10, 5, 15, null, null, 6, 20] — 6 < 10 but lives in right subtree

Tradeoff: Misses subtle inversions deeper in the tree.

2. Recurse with min/max bounds

Each recursive call carries (min, max). Node must be strictly in bounds. Left child's max = node.val; right child's min = node.val.

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

Tradeoff: Bounds propagate the global invariant. Strict < and > catch equality violations.

Workday-specific tips

Workday wants the bounds-propagation approach (NOT the inorder version, though it works too). Articulate that direct-child checks miss inversions like [10, 5, 15, null, null, 6, 20]. Use strict inequalities since BSTs disallow duplicates.

Common mistakes

  • Only checking direct children — misses cross-subtree inversions.
  • Using <= or >= for bounds — allows duplicates which violate strict BST.
  • Using Number.MIN_VALUE instead of -Infinity (Number.MIN_VALUE is the smallest positive number).

Follow-up questions

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

  • Inorder traversal — must be strictly increasing.
  • Recover Binary Search Tree (LC 99).
  • What if duplicates are allowed?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Min/max vs inorder?

Both work in O(n). Min/max recursion is cleaner and short-circuits on the first violation. Inorder requires tracking the previous node.

Why strict < and >?

BST disallows duplicates by convention. <= would permit equal keys, violating the definition.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →