98. Validate Binary Search Tree

mediumAsked at Atlassian

Validate Binary Search Tree is an Atlassian classic for testing whether you understand the recursive invariant of a BST. Return true if a given binary tree is a valid BST. The naive 'check children' answer is wrong, and Atlassian uses this exact gap to grade rigorous thinkers.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Validate BST as a recurring tree problem in round 2.
Blind (2025-09)— Atlassian threads repeatedly cite this as the problem that filters out 'looks-correct-but-isn't' candidates.

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 strictly less than the node's key; the right subtree of a node contains only nodes with keys strictly greater than the node's key; and 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's value is 4.

Approaches

1. Naive child-comparison (broken)

At each node, check left.val < val < right.val and recurse.

Time: O(n)
Space: O(h)

function isValidBSTBroken(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 isValidBSTBroken(root.left) && isValidBSTBroken(root.right);
}

Tradeoff: EXPLICITLY WRONG. Tree [5,1,4,null,null,3,6] passes this check (5>1, 5<4 fails — wait, this catches that case). The real failure: [10,5,15,null,null,6,20] — 15>10 OK, 6<15 OK locally, but 6<10 violates ancestor. Show this code first to demonstrate you understand WHY it's wrong, then fix.

2. Range propagation (canonical)

Pass (lo, hi) bounds down the recursion. At each node, val must be strictly between lo and hi; recurse left with hi=val, right with lo=val.

Time: O(n)
Space: O(h) recursion

function isValidBST(root) {
  const validate = (node, lo, hi) => {
    if (!node) return true;
    if (lo !== null && node.val <= lo) return false;
    if (hi !== null && node.val >= hi) return false;
    return validate(node.left, lo, node.val) && validate(node.right, node.val, hi);
  };
  return validate(root, null, null);
}

Tradeoff: The Atlassian-canonical answer. Carries the ancestor constraint via the bounds. Use null sentinels (not -Infinity / Infinity) because LeetCode's val range includes those numerically; null cleanly means 'no bound'.

3. In-order traversal monotonicity check

In-order traversal of a BST visits nodes in strictly ascending order. Walk in-order; fail if any node's value is <= the previous.

Time: O(n)
Space: O(h)

function isValidBSTInorder(root) {
  let prev = null;
  const inorder = (node) => {
    if (!node) return true;
    if (!inorder(node.left)) return false;
    if (prev !== null && node.val <= prev) return false;
    prev = node.val;
    return inorder(node.right);
  };
  return inorder(root);
}

Tradeoff: Elegant — uses the defining property of BST in-order traversal. Closure over prev is the subtle part; some interviewers prefer this version because it's a smaller mental model. Either this or range-propagation passes; mention both.

Atlassian-specific tips

Atlassian explicitly grades whether you spot WHY the naive child-comparison fails. Spend 30 seconds writing the broken version and constructing the counterexample tree [10,5,15,null,null,6,20] aloud — the interviewer sees you understand the bug, not just the fix. Both range-propagation and in-order pass; range is more defensible if asked 'how do you avoid global state?', in-order is more elegant. Mention both.

Common mistakes

Using <= where < is required (or vice versa) — the LeetCode spec is strictly less / strictly greater, so equal values invalidate.
Initializing bounds with Number.MIN_SAFE_INTEGER / MAX_SAFE_INTEGER — those values can legitimately appear in the tree. Use null sentinels and check for null before comparing.
On the in-order version, declaring prev inside the function — it resets to null every call. Use a closure or wrapper object.

Follow-up questions

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

Recover Binary Search Tree (LeetCode 99) — two nodes are swapped; find and swap them back. In-order traversal finds the dips.
Convert Sorted Array to BST (LeetCode 108) — opposite direction; build a balanced BST.
What if the tree's values are floats and equality is OK? Switch to <= and >= in the recursion; the rest is unchanged.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Range or in-order at Atlassian?

Either passes. Lead with range-propagation because it generalizes to more constraints (e.g., min-distance constraints) without restructuring. Mention in-order as 'and there's a more elegant traversal-based variant'. The interviewer will probably let you pick.

Why is null sentinel safer than +-Infinity?

Because LeetCode's val range is [-2^31, 2^31 - 1] in integer mode, and floats outside that range can compare incorrectly. null with an explicit guard expresses 'no bound' unambiguously. Use it.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →