Iterative binary search tree validation

You're sitting in a Bloomberg interview and the interviewer draws a binary tree on the whiteboard. "Tell me if this is a valid binary search tree," they say, "but don't use recursion." This twist immediately separates candidates who truly understand BST properties from those who have only memorized the recursive one-liner. This problem, also known as "Validate Binary Search Tree" on other platforms, tests your ability to think iteratively about tree invariants and is a favorite at companies like Bloomberg and Microsoft.

TL;DR

Use a queue-based BFS traversal where each node carries inherited min/max bounds. For the root, bounds start at (-INF, +INF). When processing a node, check that its value falls strictly within its bounds. For the left child, the upper bound tightens to the current node's value. For the right child, the lower bound tightens to the current node's value. If any node fails its bounds check, return false. This runs in O(n) time and O(n) space.

Why This Problem Matters

BST validation sits at the intersection of two fundamental skills: understanding the BST invariant and working with iterative tree traversal. The recursive version is straightforward, but the iterative version forces you to think about how information flows through a tree without the call stack doing the bookkeeping for you. That mental shift is exactly what interviewers want to see.

Binary Search Trees: The Core Invariant

A binary search tree enforces a strict ordering rule: for every node, all values in its left subtree are strictly less than the node's value, and all values in its right subtree are strictly greater.

This rule applies recursively to every subtree, not just the immediate children. That distinction is the crux of the problem.

Understanding the Problem

Given: The root of a binary tree Task: Determine whether it is a valid BST, without recursion Return: true if valid, false otherwise Constraint: All node values are between -10,000 and 10,000

Here is a valid BST where every node satisfies the ordering rule:

And here is an invalid one. Node 18 is correctly greater than its parent 15, but it also sits in the left subtree of 20, where all values must be less than 20. Since 18 is less than 20, it actually passes that check. But wait, 18 is the right child of 15, meaning it should be greater than 15 and less than 20. It is. So this tree is actually tricky to evaluate at first glance. The real violation is subtler: look at the test case "20 15 30 # 18 # 40" where # means null. Node 15 has no left child and 18 as its right child. 18 is greater than 15 (valid for right child) and less than 20 (valid for left subtree of root). This particular tree is actually invalid because 18 appears as the right child of 15, but let's look at the actual failing test case "20 15 18 10 30" to see a clear violation:

In this tree, 18 appears as the right child of 15 in the left subtree of 20. But node 18's bounds should be (15, 20), and 18 falls within that range. The real problem is node 30, which appears as the right child of 15's... actually, let me trace through the actual test case structure. The key insight is that simply checking parent-child relationships is not enough. You need to propagate bounds from every ancestor.

The Naive Trap

Many candidates write something like this on their first attempt:

// WRONG: Only checks immediate parent
boolean isValidBst(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && root.left.data >= root.data) return false;
    if (root.right != null && root.right.data <= root.data) return false;
    // This misses violations deeper in the tree!
}

This fails because a node deep in the left subtree could be greater than the root while still being less than its direct parent. The BST property is about the entire subtree, not just the immediate children.

Edge Cases

1. Null root: An empty tree is a valid BST (return true)
2. Single node: Always valid
3. Skewed tree: All nodes on one side, like 1 -> 2 -> 3 -> ...
4. Duplicate values: Strict BST ordering means duplicates are invalid

Solution Approach

The strategy is to propagate valid bounds as we traverse. Each node inherits a range (min, max) from its ancestors:

• The root starts with (Integer.MIN_VALUE, Integer.MAX_VALUE)
• A left child inherits (parent.min, parent.data) as its range
• A right child inherits (parent.data, parent.max) as its range

If a node's value does not fall strictly within its range, the tree is invalid.

We use a queue for level-order (BFS) traversal and wrap each node in an EnrichedTreeNode that carries its bounds. This keeps the traversal clean and the validation logic simple.

The queue processes nodes level by level, and each dequeued node is checked against its inherited bounds before its children are enqueued with tightened ranges.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
  public Boolean isValidBst(TreeNode root) {
    if (root == null) return true;

    Deque<EnrichedTreeNode> queue = new LinkedList<>();
    queue.offer(new EnrichedTreeNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE));

    while (!queue.isEmpty()) {
      EnrichedTreeNode node = queue.poll();

      if (!node.isValid()) return false;

      if (node.left != null) {
        queue.offer(new EnrichedTreeNode(node.left, node.min, node.data));
      }
      if (node.right != null) {
        queue.offer(new EnrichedTreeNode(node.right, node.data, node.max));
      }
    }

    return true;
  }

  class EnrichedTreeNode extends TreeNode {
    private final int min, max;

    EnrichedTreeNode(TreeNode node, int min, int max) {
      super(node.data, node.left, node.right);
      this.min = min;
      this.max = max;
    }

    boolean isValid() {
      return data > min && data < max;
    }
  }
}

Walking Through the Algorithm

Let's trace through the valid BST [10, 5, 15, 4, 6, 14, 16]:

Each node is checked against its inherited bounds before its children are enqueued with narrowed ranges. The queue ensures we process all nodes at one level before moving to the next, though any traversal order would work here since we carry the bounds explicitly.

Why an EnrichedTreeNode?

The EnrichedTreeNode pattern bundles a node with its validation metadata. Without it, you would need parallel data structures (separate queues for min/max bounds), which is error-prone and harder to read. By extending TreeNode, the enriched version carries everything the validation logic needs in one object.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. For each node, we perform a constant-time bounds check and potentially enqueue two children. There is no way to short-circuit the traversal in the general case since the invalid node could be the very last one processed.

Space Complexity: O(n)

The queue can hold up to O(n) nodes in the worst case. For a complete binary tree, the bottom level alone contains roughly n/2 nodes, all of which may be in the queue simultaneously. For a perfectly skewed tree (essentially a linked list), the queue holds at most one node at a time.

Recursive Alternative

The recursive version is more concise:

boolean isValidBst(TreeNode node, int min, int max) {
    if (node == null) return true;
    if (node.data <= min || node.data >= max) return false;
    return isValidBst(node.left, min, node.data) &&
           isValidBst(node.right, node.data, max);
}

Same O(n) time and O(n) worst-case space (call stack on skewed trees). The iterative version avoids potential stack overflow and explicitly manages traversal state, which is why interviewers specifically ask for it.

Common Pitfalls

1. Checking only the parent: The most frequent mistake. Node 18 can be a valid right child of 15 but still violate the root's constraint if it sits in the root's left subtree. Always propagate the full range.

2. Using non-strict comparison: BSTs require strict ordering. Using >= or <= in the bounds check will incorrectly accept trees with duplicate values.

3. Forgetting Integer overflow: In languages with fixed-size integers, using Integer.MIN_VALUE and Integer.MAX_VALUE as initial bounds can cause issues if node values equal those extremes. The problem constrains values to (-10000, 10000), so this is safe here. For unconstrained inputs, use long or language-specific infinity values.

4. Returning early on the wrong condition: Some candidates return true as soon as they find one valid node. The tree is only valid if every node passes.

Interview Tips

1. Clarify the BST definition: "Should I treat duplicate values as invalid?" This shows attention to detail.

2. Draw the bounds propagation: Sketch a small tree and write the (min, max) range next to each node. This makes the algorithm visually obvious.

3. Mention the recursive version first: Then pivot to iterative when asked. This demonstrates you understand both approaches and can translate between them.

4. Discuss the EnrichedTreeNode tradeoff: You could use three parallel queues (nodes, mins, maxes) instead of a wrapper class. The wrapper is cleaner but uses slightly more memory. Mentioning this shows engineering maturity.

5. Prepare for follow-ups: "How would you find the largest valid BST subtree?" or "What if the tree allows duplicates on the left?"

Key Takeaways

• The BST invariant applies to entire subtrees, not just parent-child pairs. Every node inherits a valid range from all its ancestors.
• The iterative approach uses a queue of enriched nodes carrying (min, max) bounds, avoiding recursion while maintaining O(n) time and O(n) space.
• Initial bounds of (Integer.MIN_VALUE, Integer.MAX_VALUE) for the root ensure it always passes. Left children narrow the upper bound; right children narrow the lower bound.
• This bounds-propagation technique applies to many tree validation problems, including checking if a tree is a max-heap or verifying interval constraints in segment trees.
• Always use strict inequality (> and <, not >= and <=) unless the problem explicitly allows duplicate values in the BST.

Related Problems and Practice

Once you are comfortable with iterative BST validation, these problems build on similar concepts:

• Find the kth smallest node in a BST - uses iterative in-order traversal
• Insert into a binary search tree - requires understanding BST ordering
• Lowest common ancestor in a BST - leverages BST properties for efficient search
• Convert binary tree to mirror - another iterative tree manipulation

Consistent practice builds the muscle memory for tree traversal patterns. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether you are targeting Bloomberg, Microsoft, or your next role, getting comfortable with iterative tree algorithms will pay dividends.

Solutions in Other Languages

Python

from collections import deque
from TreeNode import TreeNode


class Solution:
    def is_valid_bst(self, root: TreeNode) -> bool:
        if root is None:
            return True
        queue = deque()
        queue.append(EnrichedTreeNode(root, float('-inf'), float('inf')))
        while len(queue) > 0:
            node = queue.popleft()
            if not node.is_valid():
                return False
            if node.left is not None:
                queue.append(EnrichedTreeNode(node.left, node.min, node.data))
            if node.right is not None:
                queue.append(EnrichedTreeNode(node.right, node.data, node.max))
        return True


class EnrichedTreeNode(TreeNode):
    def __init__(self, node, min_val, max_val):
        super().__init__(node.data, node.left, node.right)
        self.min = min_val
        self.max = max_val

    def is_valid(self):
        return self.min < self.data < self.max

JavaScript

class Solution {
  isValidBst(root) {
    if (root === null) return true;
    const queue = new Queue();
    queue.enqueue(
      new EnrichedTreeNode(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY)
    );
    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      if (!node.isValid()) return false;
      if (node.left !== null) {
        queue.enqueue(new EnrichedTreeNode(node.left, node.min, node.data));
      }
      if (node.right !== null) {
        queue.enqueue(new EnrichedTreeNode(node.right, node.data, node.max));
      }
    }
    return true;
  }
}

TypeScript

class Solution {
  isValidBst(root: TreeNode | null): boolean {
    if (root === null) return true;
    const queue = new BstQueue<EnrichedTreeNode>();
    queue.enqueue(
      new EnrichedTreeNode(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY)
    );
    while (queue.nonEmpty()) {
      const node = queue.dequeue();
      if (!node.isValid()) return false;
      if (node.left !== null) {
        queue.enqueue(new EnrichedTreeNode(node.left, node.min, node.data));
      }
      if (node.right !== null) {
        queue.enqueue(new EnrichedTreeNode(node.right, node.data, node.max));
      }
    }
    return true;
  }
}

C++

#include <queue>
#include <limits>

class Solution {
public:
  bool isValidBst(TreeNode *root) {
    if (!root) return true;
    std::queue<EnrichedTreeNode> queue;
    queue.push(EnrichedTreeNode(
        root, std::numeric_limits<int>::min(), std::numeric_limits<int>::max()));
    while (!queue.empty()) {
      EnrichedTreeNode enrichedNode = queue.front();
      queue.pop();
      if (!enrichedNode.isValid()) return false;
      if (enrichedNode.node->left) {
        queue.push(EnrichedTreeNode(
            enrichedNode.node->left, enrichedNode.min, enrichedNode.node->data));
      }
      if (enrichedNode.node->right) {
        queue.push(EnrichedTreeNode(
            enrichedNode.node->right, enrichedNode.node->data, enrichedNode.max));
      }
    }
    return true;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def isValidBst(root: TreeNode): Boolean = {
    if (root == null) return true
    val queue = mutable.Queue[EnrichedTreeNode]()
    queue.enqueue(new EnrichedTreeNode(root, Int.MinValue, Int.MaxValue))
    while (queue.nonEmpty) {
      val node = queue.dequeue
      if (!node.isValid) return false
      if (node.left != null)
        queue.enqueue(new EnrichedTreeNode(node.left, node.min, node.data))
      if (node.right != null)
        queue.enqueue(new EnrichedTreeNode(node.right, node.data, node.max))
    }
    true
  }
}

Kotlin

import java.util.ArrayDeque

class Solution {
  fun isValidBst(root: TreeNode?): Boolean {
    if (root == null) return true
    val queue = ArrayDeque<NodeWithBounds>()
    queue.offer(NodeWithBounds(root, Long.MIN_VALUE, Long.MAX_VALUE))
    while (queue.isNotEmpty()) {
      val current = queue.poll()
      val node = current.node
      if (node.data <= current.min || node.data >= current.max) return false
      node.left?.let { queue.offer(NodeWithBounds(it, current.min, node.data.toLong())) }
      node.right?.let { queue.offer(NodeWithBounds(it, node.data.toLong(), current.max)) }
    }
    return true
  }

  private data class NodeWithBounds(val node: TreeNode, val min: Long, val max: Long)
}

Swift

import Foundation

class Solution {
    func isValidBst(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        var queue = [NodeWithBounds(root, Int.min, Int.max)]
        while !queue.isEmpty {
            let current = queue.removeFirst()
            if current.node.data <= current.min || current.node.data >= current.max {
                return false
            }
            if let left = current.node.left {
                queue.append(NodeWithBounds(left, current.min, current.node.data))
            }
            if let right = current.node.right {
                queue.append(NodeWithBounds(right, current.node.data, current.max))
            }
        }
        return true
    }

    private struct NodeWithBounds {
        let node: TreeNode
        let min: Int
        let max: Int
        init(_ node: TreeNode, _ min: Int, _ max: Int) {
            self.node = node
            self.min = min
            self.max = max
        }
    }
}

Ruby

class Solution
  def is_valid_bst(root)
    return true if root.nil?
    queue = [[root, -Float::INFINITY, Float::INFINITY]]
    until queue.empty?
      node, min_val, max_val = queue.shift
      return false unless node.data > min_val && node.data < max_val
      queue.push([node.left, min_val, node.data]) unless node.left.nil?
      queue.push([node.right, node.data, max_val]) unless node.right.nil?
    end
    true
  end
end

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn is_valid_bst(&self, root: Option<Box<TreeNode>>) -> bool {
        if root.is_none() { return true; }
        let mut queue: VecDeque<(&TreeNode, i64, i64)> = VecDeque::new();
        let root_ref = root.as_ref().unwrap();
        queue.push_back((root_ref, i64::MIN, i64::MAX));
        while let Some((node, min, max)) = queue.pop_front() {
            let data = node.data as i64;
            if data <= min || data >= max { return false; }
            if let Some(ref left) = node.left {
                queue.push_back((left, min, data));
            }
            if let Some(ref right) = node.right {
                queue.push_back((right, data, max));
            }
        }
        true
    }
}

Dart

import 'dart:collection';

class Solution {
  bool isValidBst(TreeNode? root) {
    if (root == null) return true;
    Queue<_NodeWithBounds> queue = Queue();
    queue.add(_NodeWithBounds(root, -1 << 62, 1 << 62));
    while (queue.isNotEmpty) {
      _NodeWithBounds current = queue.removeFirst();
      if (current.node.data <= current.min || current.node.data >= current.max)
        return false;
      if (current.node.left != null) {
        queue.add(_NodeWithBounds(current.node.left!, current.min, current.node.data));
      }
      if (current.node.right != null) {
        queue.add(_NodeWithBounds(current.node.right!, current.node.data, current.max));
      }
    }
    return true;
  }
}

PHP

class Solution {
    public function isValidBst(?TreeNode $root): bool {
        if ($root === null) return true;
        $queue = [new EnrichedTreeNode($root, PHP_INT_MIN, PHP_INT_MAX)];
        while (!empty($queue)) {
            $node = array_shift($queue);
            if (!$node->isValid()) return false;
            if ($node->left !== null) {
                $queue[] = new EnrichedTreeNode($node->left, $node->min, $node->data);
            }
            if ($node->right !== null) {
                $queue[] = new EnrichedTreeNode($node->right, $node->data, $node->max);
            }
        }
        return true;
    }
}

C#

public class Solution {
    public bool isValidBst(TreeNode? root) {
        if (root == null) return true;
        var queue = new Queue<NodeWithBounds>();
        queue.Enqueue(new NodeWithBounds(root, long.MinValue, long.MaxValue));
        while (queue.Count > 0) {
            var current = queue.Dequeue();
            var node = current.Node;
            if (node.data <= current.Min || node.data >= current.Max) return false;
            if (node.left != null)
                queue.Enqueue(new NodeWithBounds(node.left, current.Min, node.data));
            if (node.right != null)
                queue.Enqueue(new NodeWithBounds(node.right, node.data, current.Max));
        }
        return true;
    }

    private class NodeWithBounds {
        public TreeNode Node { get; }
        public long Min { get; }
        public long Max { get; }
        public NodeWithBounds(TreeNode node, long min, long max) {
            Node = node; Min = min; Max = max;
        }
    }
}