Skip to content
Codeloom
DSA

Validate Binary Search Tree — Min/Max Bounds DFS

The seductive wrong answer, the correct min/max bounds approach, and how to defend it in an interview.

·5 min read · By Codeloom
Intermediate 9 min read

What you'll learn

  • ✓Why checking only direct children fails
  • ✓The min/max bounds DFS pattern
  • ✓The inorder traversal alternative
  • ✓Common pitfalls with duplicates and integer limits

Prerequisites

Validate BST looks like a five-minute problem until you submit a five-minute solution and watch it fail. The trap is that “left is smaller, right is bigger” describes a local relationship, but a BST demands a global one. Every node has an implicit range it must live inside, and that range is the whole problem.

The Problem

Given the root of a binary tree, decide whether it is a valid binary search tree. A valid BST has:

  • All nodes in the left subtree strictly less than the current node
  • All nodes in the right subtree strictly greater than the current node
  • Both subtrees themselves valid BSTs

The constraint that often gets missed: it must hold for every descendant, not just the immediate children.

Intuition

Pass a (low, high) range down. The root starts with (-inf, +inf). When you recurse left, the upper bound becomes the current value; when you recurse right, the lower bound does. Any node outside its range fails immediately. An equivalent angle: an inorder traversal of a BST is strictly increasing — walk inorder, track the previous value, and bail if anything is out of order.

Explanation with Example

Consider the tree [5, 1, 4, null, null, 3, 6]. Visually:

  • Root 5 with range (-inf, +inf) — passes.
  • Left child 1 with range (-inf, 5) — passes.
  • Right child 4 with range (5, +inf) — fails. 4 is not greater than 5.

The naive “check children only” version would have happily compared 4 to its children 3 and 6, and missed that 4 must also exceed 5.

              5   range (-inf, +inf)  OK
           / \
 range    1   4   range (5, +inf)  FAIL
(-inf, 5)     / \
            3   6

descent rule:
go left  : high becomes node.val
go right : low  becomes node.val
Bounds tighten as DFS descends; node 4 violates (5, +inf)

Code

def isValidBST(root):
    def dfs(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

    return dfs(root, float("-inf"), float("inf"))
public boolean isValidBST(TreeNode root) {
    return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean dfs(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return dfs(node.left, low, node.val) && dfs(node.right, node.val, high);
}
bool dfs(TreeNode* node, long low, long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return dfs(node->left, low, node->val) && dfs(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) {
    return dfs(root, LONG_MIN, LONG_MAX);
}

Edge Cases

  • A single-node tree is valid.
  • An empty tree is valid by convention.
  • Duplicate values are not allowed — the comparisons must be strict.
  • Integer extremes matter. If a node holds 2**31 - 1, using regular ints as sentinels is fine in Python but breaks naive C++ ports. Use long or None as sentinels.
  • A degenerate tree shaped like a linked list still works, but recursion may need an iterative variant for very deep trees.

Complexity Analysis

The optimal DFS visits each node once and does constant work, so time is O(n). Space is O(h) for the recursion stack, where h is tree height. A balanced tree gives O(log n), a skewed one O(n). The inorder iterative version has the same bounds. For why these matter, see Big-O Notation Explained.

How to Explain It in an Interview

Open with the trap: “Checking only immediate children is wrong because a node deep in the left subtree of the root must still be less than the root.” Then offer the fix: pass an allowed range down through DFS, tightening the upper bound on left moves and the lower bound on right moves. Mention the inorder traversal alternative as a sanity check — interviewers like seeing two angles. If asked about iterative versions, point at an explicit stack or Morris traversal.

  • Kth Smallest Element in a BST (also leans on inorder)
  • Lowest Common Ancestor of a BST
  • Recover Binary Search Tree
  • Convert Sorted Array to BST

All of them reward fluency with recursive thinking.

Wrap up

Validating a BST is a vocabulary check: do you know what “valid” really means across the whole tree? Once you see that every node has an implicit range, the DFS writes itself. Memorize the min/max bounds pattern — it shows up in nearly every BST verification or construction problem you will face.

Related articles