📖 10 min read
Last updated on

Validate Binary Search Tree — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer draws a binary tree on the whiteboard and asks: “Is this a valid BST?” Your first instinct is to check each node against its parent. That approach feels right, passes simple examples, and is completely wrong. The BST property is a global constraint, not a local one, and the moment you miss that distinction the interviewer already has your answer.

This walkthrough covers how that conversation unfolds: the clarifying questions that demonstrate real BST understanding, the trap most candidates fall into, the bounds-propagation technique that fixes it, and the edge cases interviewers use to test whether your solution is truly correct.

The Problem

Given the root of a binary tree, determine whether 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 values strictly less than the node’s value.
  • The right subtree of a node contains only nodes with values strictly greater than the node’s value.
  • Both the left and right subtrees must also be valid BSTs.

(LeetCode #98)

Example 1

Input

    2
   / \
  1   3

root = [2, 1, 3]

Output true

Example 2

Input

        10
       /  \
      5    15
     / \   / \
    3   7  6  20

root = [10, 5, 15, 3, 7, 6, 20]

Output false

In Example 1, node 1 is to the left of 2 (less than) and node 3 is to the right (greater than), valid. In Example 2, the tree looks perfectly healthy at first glance. Every parent-child relationship checks out. Yet the tree is invalid: node 6 sits in the right subtree of 10, which means it must be greater than 10, but 6 < 10. This is exactly the violation that trips most candidates up.

Valid BST [2,1,3] marked as valid (✓) versus invalid BST [10,5,15,3,7,6,20] marked as invalid (✗) with node 6 violating the root bound.

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

This problem is a litmus test for whether candidates understand BST invariants globally, not just locally. A surprising number of candidates who “know” BSTs still fail this problem because they reason node-by-node instead of thinking about constraints that propagate through the tree.

SkillWhat Interviewers Observe
BST invariant understandingDo you know the rule applies globally, not just to parent-child pairs?
Recursive reasoningCan you design a recursive function that carries state (bounds) downward?
Handling edge casesDo you account for duplicate values, negative numbers, and INT_MIN/INT_MAX?
Alternative approach awarenessCan you connect this to in-order traversal producing a sorted sequence?
Communication clarityCan you explain why the naive local-check approach fails before proposing the fix?

Step 1: Clarifying Questions

A few targeted questions here signal that you understand the problem deeply before touching the keyboard.

1. Are duplicate values allowed? The standard BST definition requires strictly less than and strictly greater than, making duplicates invalid. But some BST variants allow duplicates in one subtree. Confirming this upfront avoids an off-by-one error in your comparison operators.

2. What should I return for an empty tree? An empty tree (null root) is vacuously a valid BST. Confirming this lets you write your base case cleanly and shows you think about null inputs.

3. What are the constraints on node values? If values can be as large as Integer.MAX_VALUE or as small as Integer.MIN_VALUE, using those as initial bounds causes a subtle overflow bug (in languages like Java/C++). In Python, this isn’t an issue due to arbitrary precision integers, but asking shows platform awareness.

4. Is this guaranteed to be a binary tree structure, or could it have cycles? In an interview context, the input is almost always well-formed, but asking signals defensive thinking and an understanding that an ill-formed graph would cause infinite recursion.

5. Are we validating the structure as well, or only the values? This confirms scope. The problem only asks about value constraints, not whether the tree is balanced or complete.

Step 2: A First (Non-Optimal) Idea

The most common first instinct, and the most common wrong answer, is the local comparison approach: for every node, check that its left child is less than it and its right child is greater than it.

def is_valid_bst_naive(root):
    if not root:
        return True
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False
    return is_valid_bst_naive(root.left) and is_valid_bst_naive(root.right)

This looks right. It even passes many test cases. But it is wrong.

Consider this tree:

        10
       /  \
      5    15
     / \   / \
    3   7  6  20

The local check passes everywhere: 3 < 5 ✓, 7 > 5 ✓, 5 < 10 ✓, 6 < 15 ✓, 20 > 15 ✓, 15 > 10 ✓. Every single parent-child pair looks valid. But this is not a valid BST: node 6 is in the right subtree of 10, meaning it must be greater than 10, yet 6 < 10. The local check cannot catch this because it never compares 6 against 10, only against its direct parent 15.

This is the trap. Interviewers are specifically looking to see if you fall into it, or if you recognize and articulate why it fails.

Step 3: The Key Insight

Every node in a BST must satisfy constraints set by all of its ancestors, not just its parent. When you go left, the current node’s value becomes the new upper bound. When you go right, it becomes the new lower bound. Start with (-infinity, +infinity) at the root and tighten the window as you descend. If any node falls outside its valid range, return False.

So instead of checking a node against its parent, you need to check it against a valid range, a (min_val, max_val) window that tightens as you descend the tree:

  • When you go left, the current node’s value becomes the new upper bound for the entire left subtree.
  • When you go right, the current node’s value becomes the new lower bound for the entire right subtree.

There’s also an elegant alternative approach worth mentioning: in-order traversal of a valid BST always produces a strictly increasing sequence. If you perform an in-order traversal and find any value that is not strictly greater than the previous one, the tree is invalid.

Step 4: Optimal Strategy

  1. Define a recursive helper function validate(node, min_val, max_val).
  2. Base case: If node is None, return True, an empty subtree is always valid.
  3. Bounds check: If node.val <= min_val or node.val >= max_val, return False, this node violates its inherited constraint.
  4. Recurse left: Call validate(node.left, min_val, node.val), the current node’s value becomes the new upper bound for the left subtree.
  5. Recurse right: Call validate(node.right, node.val, max_val), the current node’s value becomes the new lower bound for the right subtree.
  6. Return True only if both recursive calls return True.
  7. Kick off the recursion from the root with validate(root, -infinity, +infinity).

Python Implementation

import math

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_bst(root: TreeNode) -> bool:
    def validate(node, min_val, max_val):
        # An empty subtree is always valid
        if not node:
            return True

        # This node's value must fall strictly within the inherited bounds
        if node.val <= min_val or node.val >= max_val:
            return False

        # Recurse: tighten the upper bound going left, lower bound going right
        left_valid = validate(node.left, min_val, node.val)
        right_valid = validate(node.right, node.val, max_val)

        return left_valid and right_valid

    return validate(root, -math.inf, math.inf)

Let’s trace through Example 2 ([10, 5, 15, 3, 7, 6, 20]):

  • validate(10, -inf, +inf) → 10 is in bounds ✓
    • validate(5, -inf, 10) → 5 is in bounds ✓
      • validate(3, -inf, 5) → 3 is in bounds ✓ → both children None → True
      • validate(7, 5, 10) → 7 is in bounds ✓ → both children None → True
    • validate(15, 10, +inf) → 15 is in bounds ✓
      • validate(6, 10, 15) → 6 <= 10 → False ✗

Notice that the violation isn’t caught until we reach node 6, three levels deep, and only because it inherited the lower bound of 10 from the root. A local parent-child check at node 6 would have seen 6 < 15 and passed it. The bounds approach catches what the naive approach misses.

Bonus: In-Order Traversal Approach

def is_valid_bst_inorder(root: TreeNode) -> bool:
    prev = [-math.inf]  # Use a list to allow mutation inside the nested function

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        # Each node visited in-order must be strictly greater than the previous
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)

Both approaches are O(n) time and O(h) space where h is the tree height. The bounds-propagation approach is generally preferred in interviews because it’s easier to reason about and explain verbally.

Time & Space Complexity

AspectComplexityExplanation
TimeO(n)Each node is visited exactly once
Space (best case)O(log n)Balanced tree: recursion depth equals tree height
Space (worst case)O(n)Skewed tree: recursion depth equals number of nodes

Time: Every node is visited exactly once in a single DFS traversal.

Space: The space complexity is determined by the call stack depth, which equals the height of the tree. For a balanced BST, that’s O(log n). For a degenerate tree (essentially a linked list), it degrades to O(n).

Common Interview Mistakes

  1. The local-check trap. Checking only parent-child relationships is the most common wrong answer for this problem. If you catch yourself writing this, stop, explain why it’s insufficient, and pivot to the bounds approach. Catching your own mistake and correcting it clearly is actually impressive.

  2. Using INT_MIN and INT_MAX as initial bounds in statically typed languages. In Java or C++, using Integer.MIN_VALUE as the initial lower bound fails when a node has exactly that value. Use -infinity (or Long.MIN_VALUE as a workaround). In Python, math.inf is always safe.

  3. Using <= vs < incorrectly. BSTs require strictly less than and strictly greater than. Using < instead of <= in your bounds check allows equal values through, which is wrong for the standard definition. Get the comparison operators right.

  4. Forgetting that None nodes are valid. Some candidates add if not node: return False, which would make every leaf invalid. An absent child means there’s nothing to violate constraints: always return True for null nodes.

  5. Not explaining the approach before coding. The bounds-propagation insight is genuinely non-obvious. Interviewers want to hear you articulate why local checks aren’t enough and what you’re passing down in the recursive calls before you start writing.

  6. Hardcoding bounds as 0 or arbitrary values. Some candidates initialize with min_val = 0 or min_val = -1000, forgetting that valid BST values can be negative or very large. Always use actual infinity.

  7. Confusing the in-order approach and forgetting to track the previous node correctly. If you use the in-order traversal approach, you need a way to persist the previous value across recursive calls, either through a mutable container (list), a class variable, or by threading it through the return value. Forgetting this makes the approach silently incorrect.

What a Strong Candidate Sounds Like

“My first instinct is to check each node against its immediate parent, but I know that’s wrong. It only catches local violations, not global ones. A node deep in the right subtree could be less than the root, and a parent-child check would miss that. The right approach is to propagate a valid range down the tree. Every node inherits a (min, max) window from its ancestors, and we tighten that window as we recurse: going left, the current value becomes the new ceiling; going right, it becomes the new floor. I’ll start with (-infinity, +infinity) at the root and return False the moment any node falls outside its window. Let me trace through the example quickly and then code it up.”

This response shows: the insight was reasoned, not memorized; the candidate identified the trap before falling into it; they thought about the recursive structure before touching the keyboard.

Example Interview Dialogue

Interviewer: Why doesn’t checking each node against its direct parent work?

Candidate: Because the BST property is a global constraint, not a local one. Every node in a left subtree must be less than all of its ancestors, not just its immediate parent. So if I have a node deep in the right subtree that’s still less than the root, a parent-child check won’t catch it. The bounds approach fixes this by carrying the full constraint window all the way down.

Interviewer: What’s the space complexity of your recursive solution?

Candidate: It’s O(h) where h is the height of the tree, because that’s the maximum depth of the call stack. For a balanced tree, that’s O(log n). For a completely skewed tree, essentially a linked list, it degrades to O(n). If the interviewer is concerned about stack overflow on pathological inputs, you could convert this to an iterative solution using an explicit stack, which has the same space complexity but avoids recursion limits.

Interviewer: How would you solve it iteratively?

Candidate: Same idea: use an explicit stack where each entry is a (node, min_val, max_val) tuple. Pop a node, check its bounds, then push its children with tightened bounds. A standard depth-first traversal with bounds threaded through the stack entries.

Validate Binary Search Tree is the entry point to the BST invariant family. These problems all depend on understanding how BST properties propagate through the tree:

Practice This in a Mock Interview

Reading through this explanation makes the bounds-propagation approach feel obvious. But this problem has a specific failure mode in interviews: the local-check approach feels convincingly correct, and without a clear mental model of why bounds propagation is necessary, you may not catch your own mistake in time.

The gap between understanding and performing is real. The only way to make the bounds-propagation structure and the edge cases feel automatic is deliberate practice under realistic conditions: a timer, an interviewer asking follow-up questions, and immediate feedback on where you hesitated.

Start a mock interview for Validate Binary Search Tree on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →