Skip to main content

98. Validate Binary Search Tree

mediumAsked at Linear

Check that every node in a binary tree satisfies the BST property. Linear uses this to see if you avoid the common trap of only comparing a node to its direct parent — the BST constraint is global, not local.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Cited in Linear SWE onsite reports as a tree problem that tests global constraint reasoning.
  • Blind (2025-11)— Mentioned in multiple Linear interview threads as a medium tree question.

Problem

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

Explanation: The root node's value is 5 but its right child is 4, which is not > 5.

Approaches

1. Wrong approach: local parent comparison only

Compare each node only to its direct parent. Fails on trees like [5,4,6,null,null,3,7] where node 3 is less than root 5 but in the right subtree.

Time
O(n)
Space
O(n)
// INCORRECT — shown to illustrate the common mistake
function isValidBST_WRONG(root) {
  function dfs(node, parent, isLeft) {
    if (!node) return true;
    if (isLeft && node.val >= parent.val) return false;
    if (!isLeft && node.val <= parent.val) return false;
    return dfs(node.left, node, true) && dfs(node.right, node, false);
  }
  return dfs(root.left, root, true) && dfs(root.right, root, false);
}

Tradeoff: Incorrectly validates [5,4,6,null,null,3,7] as a BST even though 3 is in the right subtree of 5. The BST constraint is global — every node has a valid range inherited from all ancestors.

2. Valid range propagation (optimal)

Recurse with a [min, max] valid range for each node. A node is valid only if min < node.val < max. Narrow the range as you descend.

Time
O(n)
Space
O(n)
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(n) stack space. Using -Infinity/Infinity as initial bounds avoids integer edge cases cleanly. Note the strict inequalities — BSTs do not allow duplicate values.

Linear-specific tips

Lead by pointing out the trap: 'The naive approach only compares a node to its parent, which misses global violations. I need to pass down a valid range [min, max] for each subtree.' Linear interviewers specifically test whether you arrive at this insight independently — it's the key intellectual moment for this problem.

Common mistakes

  • Only comparing to the direct parent — the BST constraint applies to all ancestors, not just the immediate parent.
  • Using <= or >= instead of strict < and > — BSTs do not allow equal values; duplicates make a tree invalid.
  • Initializing with integer min/max values — Node.val can equal Integer.MIN_VALUE or MAX_VALUE, so use -Infinity and Infinity.

Follow-up questions

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

  • Kth Smallest Element in a BST (LC 230) — in-order traversal naturally gives sorted order.
  • Insert into a Binary Search Tree (LC 701) — BST insertion without rebalancing.
  • What if the tree allows duplicate values? How does the validity rule change?

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 -Infinity and Infinity instead of null?

They work as natural bounds without requiring null checks in the comparison. Node.val can be Integer.MIN_VALUE or MAX_VALUE, so null/sentinel values might clash — Infinity avoids this.

Why are the inequalities strict?

By definition, a BST requires left < root < right with no equality. A node equal to its ancestor is invalid.

Can you solve this with in-order traversal?

Yes — in-order traversal of a valid BST produces a strictly increasing sequence. Track the previous value and check that each new value is strictly greater. Same O(n) complexity.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →