Skip to main content

28. Validate Binary Search Tree

mediumAsked at Apple

Verify that every node in a binary tree satisfies the full BST invariant — Apple's file system and UI accessibility tree code depends on validated sorted structures, making this a core screening question for roles touching CoreData or UIAccessibility.

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: the left subtree of a node contains only nodes with keys less than the node's key; the right subtree contains only nodes with keys greater than the node's key; and both subtrees must also be valid BSTs.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1
  • Node values may include INT_MIN and INT_MAX — use null bounds, not numeric sentinels

Examples

Example 1

Input
root = [2,1,3]
Output
true

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false

Explanation: Root's right child 4 is less than root 5

Approaches

1. Naive recursive (left/right child only)

Check only immediate children. WRONG — fails for nodes violating ancestor bounds deep in the tree.

Time
O(n)
Space
O(h)
// INCORRECT — included to illustrate the common mistake
function isValidBST(root) {
  if (!root) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBST(root.left) && isValidBST(root.right);
}

Tradeoff:

2. Bounded DFS (min/max propagation)

Pass valid range [min, max] down the recursion. Each node must lie strictly within its inherited bounds — this catches violations anywhere in the tree.

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

Tradeoff:

Apple-specific tips

Apple interviewers almost always present the naive solution first and ask 'is this correct?' — they want to see you spot the ancestor-bound violation. The tree [10, 5, 15, null, null, 6, 20] is a canonical trap: 6 is left-child of 15 and looks locally valid, but violates root's right-subtree constraint. Walk through this example proactively. Use null bounds (−∞/+∞) rather than INT_MIN/INT_MAX to handle nodes whose values are exactly at integer boundaries — Apple hardware teams care about edge cases at machine limits.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →