Skip to main content

22. Validate Binary Search Tree

mediumAsked at Unity

Confirm that every node in a binary tree respects the BST ordering invariant — the same integrity check Unity's scene serializer runs on the transform-hierarchy tree to ensure no child's world-space sort order violates its parent's bounds.

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 BST is valid if the left subtree of every node contains only nodes with keys strictly less than the node's key, the right subtree contains only nodes with keys strictly greater, and both subtrees are also valid BSTs.

Constraints

  • The number of nodes 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 right child is 4 which is less than the root 5.

Approaches

1. In-order traversal to array

In-order traversal of a BST yields a strictly increasing sequence. Collect all values and verify no element is >= its successor.

Time
O(n)
Space
O(n)
function isValidBST(root) {
  const vals = [];
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    vals.push(node.val);
    inorder(node.right);
  }
  inorder(root);
  for (let i = 1; i < vals.length; i++) {
    if (vals[i] <= vals[i - 1]) return false;
  }
  return true;
}

Tradeoff:

2. Recursive bounds propagation

Pass min and max bounds down the tree. Each node must be strictly within (min, max). Left subtree tightens the upper bound; right tightens the lower bound.

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:

Unity-specific tips

Unity prefers the bounds-propagation approach because it mirrors how the engine validates scene-hierarchy constraints top-down — phrase the min/max as inherited world-space bounds that each child node must stay within, and mention the O(h) stack depth is safe for balanced scene trees.

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 Unity interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →