Skip to main content

23. Validate Binary Search Tree

mediumAsked at Adobe

Determine if a binary tree is a valid BST. Adobe asks this to test whether candidates understand the global invariant (not just local parent-child comparisons) — a level of rigor that mirrors validating hierarchical constraint systems in document structure and layout engines.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2025-11)— Adobe SDE-II candidates report BST validation as a standard tree problem in coding rounds.
  • LeetCode Discuss (2026-01)— Adobe interviewers use BST validate to test understanding of tree invariants vs. local conditions.

Problem

Given the root of a binary tree, determine if it is a valid binary search tree. 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 only nodes with keys greater; 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

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 has value 4 which is < root 5.

Approaches

1. Naive: check only immediate parent-child

For each node, only verify left.val < node.val < right.val. This misses violations deeper in the tree.

Time
O(n)
Space
O(h)
// WRONG — this fails on [5,4,6,null,null,3,7]
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: Incorrect — misses cases like [5,4,6,null,null,3,7] where 3 is in the right subtree of 5 but still less than 5.

2. DFS with min/max bounds propagation

Pass down valid range (min, max) to each node. For the left child, the upper bound tightens to the current node's value. For the right child, the lower bound tightens. A node is valid only if min < node.val < max.

Time
O(n)
Space
O(h)
function isValidBST(root) {
  function 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: O(n) time, O(h) space for the call stack. The bounds-propagation approach correctly enforces the global BST invariant. Adobe interviewers specifically look for -Infinity/Infinity initialization to handle integer boundary nodes.

Adobe-specific tips

Adobe interviewers frequently use the naive local-check as a trap — walk through the [5,4,6,null,null,3,7] counterexample immediately to show you understand why local checks fail. Also be ready for the in-order traversal approach: a valid BST produces a strictly increasing in-order sequence; validate by checking each visited value against the previous.

Common mistakes

  • Using left.val < root.val && right.val > root.val (local check only) — misses deeper violations.
  • Initializing bounds with Integer.MIN_VALUE/MAX_VALUE instead of -Infinity/Infinity — fails on nodes with those exact values.
  • Using <= instead of < for strict inequality — equal values violate the BST property.

Follow-up questions

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

  • Recover BST (LC 99): two nodes are swapped; restore the BST.
  • Kth Smallest Element in a BST (LC 230): uses in-order traversal.
  • How would you validate a BST using Morris traversal (O(1) space, no recursion stack)?

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 use -Infinity and Infinity as initial bounds?

Node values can be any 32-bit integer including INT_MIN and INT_MAX. Using Number.MIN_SAFE_INTEGER would fail on nodes with those extreme values. -Infinity and Infinity are always outside any valid integer, so they work universally.

What is the in-order traversal approach?

A BST in-order traversal visits nodes in strictly ascending order. Traverse in-order, track the previous value, and return false if any current value is <= previous. This is an elegant alternative with the same O(n) time, O(h) space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →