Check if a Tree is a BST or BT | Validate a BST

Validating a Binary Search Tree (BST) is a fundamental problem in data structures and algorithms. The core challenge goes beyond merely checking immediate left and right children; it requires ensuring that every node in a subtree respects global boundary constraints set by all of its ancestors.

1. Why Do We Need This? (Problem Statement & Status Quo)

A Binary Search Tree (BST) is a hierarchical data structure characterized by specific ordering properties:

• Left Subtree: Every node to the left must contain a value strictly smaller than the parent node.
• Right Subtree: Every node to the right must contain a value strictly greater than the parent node.

The Naive Trap

A common misconception when validating a BST is to check only the immediate children of each node (i.e., left.val < current.val < right.val).

In the tree above, while 50's immediate right child is 70 (which is greater than 50), the node 40 is placed in the left subtree of 70. Locally, 40 < 70 looks fine, but globally, 40 violates the rule that everything in the right subtree of 50 must be greater than 50.

2. Core Mental Model / Analogy: The Bounded Range Strategy

To solve this globally, we cannot look at local relationships in isolation. Instead, we introduce a Valid Range Strategy for every single node.

Real-Life Analogy: Think of passing down inheritance rules or security clearance brackets. As you move deeper down a family tree or corporate hierarchy, every descendant must fit within a narrower set of boundaries established by all preceding ancestors.

Every node must lie strictly between a Minimum Bound and a Maximum Bound:

• When we start at the root, the valid range is effectively negative infinity to positive infinity (-∞, +∞).
• When we go to the left child, our upper bound updates to the current node's value, while the minimum bound remains unchanged.
• When we go to the right child, our lower bound updates to the current node's value, while the maximum bound remains unchanged.

3. Step-by-Step Evolution of the Validation Flow

Let us trace how boundaries propagate through a tree during validation:

1. At the Root (30): Range is (-∞, +∞). 30 falls within this range. Valid so far.
2. Moving Left (13): Upper bound becomes 30. Range is (-∞, 30). 13 is valid.
3. Moving Left from 13 (6): Upper bound becomes 13. Range is (-∞, 13). 6 is valid.
4. Moving Right from 13 (15): Lower bound becomes 13, upper bound is 30. Range is (13, 30). 15 is valid.
5. Moving Right from Root (50): Lower bound becomes 30. Range is (30, +∞). 50 is valid.

If any node's value falls outside its designated [MIN, MAX] window, we immediately flag the tree as an invalid BST.

4. Real-World Practical Pitfalls & Edge Cases

When implementing this algorithm, developers often run into specific edge cases:

• Integer Overflow/Underflow: Since range bounds can stretch to infinity, using standard 32-bit integers (int.MIN_VALUE / int.MAX_VALUE) can cause bugs if a node actually contains those exact boundary values. Using 64-bit integers (long in Java/C++) prevents overflow issues.
• Duplicate Values: Standard BST definitions require strict inequalities (< and >). If duplicate values are present, the algorithm must account for whether duplicates belong strictly on one side.
• Null Nodes: Reaching a null node means we have successfully traversed past a leaf. Null nodes are always valid BST components and should return true.

5. Complete Flow Walkthrough

Here is the recursive validation flow when evaluating a node:

6. Implementation Code (Java & C++)

Below is the clean, production-ready recursive implementation for validating a BST.

Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Solution {
    public boolean isValidBST(TreeNode root) {
        // Use Long.MIN_VALUE and Long.MAX_VALUE to prevent integer overflow bugs
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long minVal, long maxVal) {
        // Base case: an empty tree/subtree is a valid BST
        if (node == null) {
            return true;
        }
        
        // Check if the current node violates the allowed range boundaries
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }
        
        // Recursively validate left and right subtrees with updated bounds
        return validate(node.left, minVal, node.val) && 
               validate(node.right, node.val, maxVal);
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of BST: Every node to the left is smaller, and every node to the right is larger than the parent node.
• Flaw of Local Checks: Validating only immediate children fails because values deeper in subtrees can violate ancestor constraints globally.
• The Bounded Range Strategy: Solve this by passing down valid lower and upper bounds (min and max) to every recursive child call.
• Boundary Updates on Traversal:
  • Going left updates the maximum bound to the current node's value.
  • Going right updates the minimum bound to the current node's value.
• Overflow Prevention: Use 64-bit integers (long) for bounds to prevent edge cases involving extreme integer limits.
• Time Complexity: Optimal performance runs in $O(N)$ time by visiting each node once.
• Space Complexity: Requires $O(H)$ auxiliary stack space proportional to the height of the tree.