How to Validate if a Given Binary Tree is a Valid Binary Search Tree (BST)

You can validate a binary search tree by performing a depth-first traversal while propagating permissible value ranges (min, max) to each node, ensuring every value falls strictly within its assigned bounds.

The kdn251/interviews repository provides multiple Java implementations demonstrating how to validate if a given binary tree adheres to BST ordering rules. This article examines the range-based validation algorithm used throughout the codebase, including two distinct approaches for handling boundary conditions in ValidBinarySearchTree.java and ValidateBinarySearchTree.java.

Understanding the BST Validation Problem

A binary search tree (BST) must satisfy the ordering invariant for every node: all values in the left subtree must be strictly less than the node's value, and all values in the right subtree must be strictly greater. Merely checking that a node's immediate children obey this rule is insufficient—descendant nodes anywhere in the subtree must also satisfy the constraint relative to the original ancestor.

For example, a node with value 5 might have a right child with value 10, but if that right child has a left child with value 3, the tree is invalid because 3 violates the lower bound established by the root.

The Range-Based Validation Algorithm

The most reliable method to verify BST properties is a depth-first traversal that tracks the permissible value range for each node. Instead of comparing only against the parent, each node inherits constraints from all its ancestors.

The algorithm works as follows:

1. Initialize the recursion with the full integer range (negative infinity to positive infinity).
2. At each node, verify the value lies strictly within the open interval (min, max). If not, return false.
3. Recurse on the left child with range (min, node.val) and the right child with range (node.val, max).
4. Base case: A null child is always valid.

This approach guarantees that every node satisfies the BST constraint relative to all its ancestors, not just its immediate parent.

Java Implementation Examples

The kdn251/interviews repository contains two concrete implementations of this algorithm, each handling boundary conditions differently.

Using Integer Bounds with Null Checks

The file cracking-the-coding-interview/chapter-four-trees-and-graphs/ValidBinarySearchTree.java implements the range check using Integer objects, where null represents an unbounded side. The core logic resides in the checkBST method on lines 8-19.

public class ValidBinarySearchTree {
    boolean checkBST(TreeNode n) {
        return checkBST(n, null, null);
    }
    
    boolean checkBST(TreeNode n, Integer min, Integer max) {
        if (n == null) return true;
        
        if ((min != null && n.val <= min) || (max != null && n.val >= max)) {
            return false;
        }
        
        return checkBST(n.left, min, n.val) && checkBST(n.right, n.val, max);
    }
}

This implementation requires null checks at each comparison but works correctly for standard integer ranges found in most interview scenarios.

Using Long Sentinel Values

The file leetcode/tree/ValidateBinarySearchTree.java (also found in company/facebook/ValidateBinarySearchTree.java) avoids null checks by using long sentinel values for the initial bounds. The recursive method validBSTRecursive is defined on lines 37-44.

public class ValidateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return validBSTRecursive(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validBSTRecursive(TreeNode root, long min, long max) {
        if (root == null) return true;
        
        if (root.val <= min || root.val >= max) {
            return false;
        }
        
        return validBSTRecursive(root.left, min, root.val) && 
               validBSTRecursive(root.right, root.val, max);
    }
}

This approach is generally safer for extreme integer values because it uses the wider long range for initial bounds, preventing overflow issues when comparing against Integer.MIN_VALUE or Integer.MAX_VALUE.

Example Usage

Both implementations validate the same tree structures:

// Minimal TreeNode definition used by the repository
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// Example 1 – a valid BST
TreeNode rootValid = new TreeNode(2);
rootValid.left  = new TreeNode(1);
rootValid.right = new TreeNode(3);

ValidateBinarySearchTree validator = new ValidateBinarySearchTree();
System.out.println(validator.isValidBST(rootValid)); // prints true

// Example 2 – an invalid BST (left child greater than root)
TreeNode rootInvalid = new TreeNode(2);
rootInvalid.left  = new TreeNode(3);   // violates BST rule
rootInvalid.right = new TreeNode(1);

System.out.println(validator.isValidBST(rootInvalid)); // prints false

Complexity Analysis

Both implementations share the same computational characteristics:

• Time Complexity: O(N), where N is the number of nodes in the tree. The algorithm visits each node exactly once to verify its value against the permissible range.
• Space Complexity: O(H), where H is the height of the tree. This accounts for the recursion stack depth. In the worst case (a completely unbalanced tree), H equals N, resulting in O(N) space. For a balanced tree, the space complexity is O(log N).

Summary

• Validate if a given binary tree is a valid Binary Search Tree by performing a depth-first traversal while propagating valid value ranges (min, max) to each node.
• The kdn251/interviews repository provides two robust Java implementations: ValidBinarySearchTree.java using Integer bounds with null checks, and ValidateBinarySearchTree.java using long sentinel values.
• Both approaches guarantee O(N) time complexity and correctly enforce the strict ordering invariant required for BST validation.

Frequently Asked Questions

What is the most efficient way to validate a BST?

The most efficient way to validate a BST is the range-based depth-first search algorithm, which achieves O(N) time complexity by visiting each node exactly once while tracking permissible value bounds. This approach is more efficient than in-order traversal with array storage, which requires O(N) additional space, and more reliable than simple parent-child comparisons that fail to catch ancestor constraint violations.

Why use Long instead of Integer for BST validation?

Using Long (specifically Long.MIN_VALUE and Long.MAX_VALUE) as sentinel bounds prevents integer overflow issues when the tree contains values at the extreme ends of the int range. If you initialize bounds with Integer.MIN_VALUE or Integer.MAX_VALUE, a node with that exact value would fail the boundary check incorrectly. The long type provides a wider range that safely encompasses all possible int values.

Can I validate a BST using in-order traversal?

Yes, you can validate a BST using in-order traversal because a valid BST produces a strictly increasing sequence when traversed in-order. The algorithm performs an in-order traversal while keeping track of the previously visited node's value; if the current node's value is not greater than the previous value, the tree is invalid. However, this approach typically requires O(N) space to store the traversal sequence or O(H) space for a recursive implementation with state tracking, making the range-based method more intuitive for most interview scenarios.

What is the time complexity of BST validation?

The time complexity of BST validation is O(N), where N represents the number of nodes in the tree, because any correct algorithm must examine each node at least once to verify the BST property. The auxiliary space complexity is O(H), where H is the height of the tree, due to the recursion stack. In a balanced BST, this results in O(log N) space, while a completely unbalanced (skewed) tree requires O(N) space.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}