Validate Binary Search Tree with Bounds Propagation

Validating whether a binary tree satisfies BST properties is a classic DSA problem requiring careful consideration of node value constraints. This solution demonstrates bounds propagation as an elegant approach to ensure each node adheres to its valid range constraints.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be mutated, or must we work with a copy?
2. What is the expected return format — boolean, index, or something else?
3. Are duplicate values allowed in the input structure?
4. What is the size constraint for the input — can we assume it's within reasonable limits for O(n) solutions?
5. Should we aim for O(n) time complexity, or is O(n log n) acceptable?

Restate the pattern or problem type in your own words: This is a classic tree validation problem where we must verify that a given binary tree satisfies the properties of a valid Binary Search Tree (BST). A valid BST requires that for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This constraint must hold recursively for all nodes in the tree.

Clarify the signal words and constraint shape that point to it: Key indicators include "binary search tree", "validate BST", "tree structure", and the requirement that values must maintain a specific ordering relationship. The problem typically involves a tree node structure with left and right child pointers, and the constraint that each node's value must fall within a valid range determined by its ancestors.

Note any assumptions you are making: I'm assuming the input is a valid binary tree structure with proper left/right child relationships. I'm also assuming that duplicate values are not allowed in a strict BST (though some variations permit duplicates). The tree is likely represented using standard TreeNode objects with value, left, and right fields.

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily designed for static validation problems where the entire tree structure is available upfront. It's not naturally suited for streaming scenarios where nodes arrive one at a time, though the bounds propagation approach could be adapted for such cases with additional bookkeeping.

The core insight is that instead of checking local constraints at each node, we maintain global bounds that each node must satisfy based on its position in the tree hierarchy. This allows us to validate the entire structure with a single traversal.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Validate" or "check" BST properties
• "Is valid BST" or "valid binary search tree"
• Input given as array representation or tree nodes
• Constraints like "all nodes in left subtree are less than root" and "all nodes in right subtree are greater than root"
• Range or bounds constraints on node values

Why this pattern fits better than alternatives: This pattern is superior to naive approaches that check local constraints only (e.g., checking if left child < parent and right child > parent) because it properly validates the global BST property. Unlike inorder traversal approaches that require O(n) space, bounds propagation can validate in O(1) space with a single pass. It's more efficient than building the entire tree and validating, especially for streaming or online scenarios.

Conditions where variations apply:

• For sorted arrays, binary search tree validation can be optimized using the fact that in-order traversal should yield strictly increasing values
• For streaming data, we might need to maintain bounds as new elements arrive, making this approach more suitable than batch processing
• When we have additional constraints like "no duplicate values allowed" or "only integer values", the bounds must be adjusted accordingly

Core insight: The key insight is that each node in a valid BST must satisfy a range constraint based on its ancestors. Rather than checking local relationships, we propagate and maintain valid bounds for each node as we traverse the tree. This ensures that every node respects all of its ancestors' constraints, making it a robust validation mechanism.

This pattern is particularly effective when we're given the tree structure and need to validate that it adheres to BST properties without needing to reconstruct or reorganize the data.

3. Approach Evolution

Interview communication script:

My first instinct is to check if each node satisfies the BST property by ensuring that for any node, its value lies within a valid range. But that's O(n²) in the worst case if I have to check all ancestors for each node, so let me think about how to optimize this. I notice that if I maintain bounds for each node during traversal, I can reduce it to O(n) by checking just the immediate parent constraints. The key insight is that instead of validating each node against all ancestors, I can propagate the valid range from parent to child nodes.

Let me think about this more carefully. The brute force approach would be to for each node, traverse up to the root and check that the node's value is within the valid range determined by its ancestors. But that's inefficient because we're doing redundant work - we're checking the same constraints multiple times.

The improved approach is to realize that each node has a valid range [min, max] where min and max are determined by the path from root to that node. For example, if we're at a node in the left subtree of some parent with value 10, then all nodes in that subtree must be less than 10. Similarly, if we're in the right subtree of a parent with value 5, then all nodes in that subtree must be greater than 5.

The final approach uses recursive bounds propagation where we pass down the valid range for each node. At each step, we validate that the current node's value is within its allowed bounds, and then recursively process children with updated bounds. This ensures we never revisit nodes or perform redundant checks.

Important invariants that must hold:

1. Each node's value must be within its valid [min, max] range
2. For left child: max = parent's value (exclusive)
3. For right child: min = parent's value (exclusive)

Brute-force approach and why it is not ideal:

The brute force approach would involve checking for each node whether its value satisfies the BST property by traversing up to the root and validating against all ancestors. For each node, we'd need to check:

• Is the node's value greater than all values in its left subtree?
• Is the node's value less than all values in its right subtree?

This leads to O(n²) time complexity in worst case because we're doing redundant checks - the same ancestor validations happen multiple times across different nodes.

Improved approach and the key optimization:

The key optimization is bounds propagation. Instead of checking each node against all ancestors, we maintain the valid range [min, max] that a node must satisfy. When we move to a left child, the upper bound becomes the parent's value (exclusive). When we move to a right child, the lower bound becomes the parent's value (exclusive).

This way, we only process each node once and validate it against its direct constraints rather than all ancestors.

Final approach with step-by-step reasoning:

1. Start with root node and set initial bounds as negative infinity to positive infinity
2. For each node, validate that its value is within [min, max] bounds (inclusive)
3. If valid, recursively process left child with updated upper bound = current node's value
4. If valid, recursively process right child with updated lower bound = current node's value
5. Return true if all validations pass

The algorithm works because:

• Each node is validated against its direct constraints from the path to root
• Bounds propagate correctly through the tree structure
• We never revisit nodes, ensuring linear time complexity

Important invariants that must hold:

1. For any node with value v, if it's in left subtree of parent with value p, then v < p
2. For any node with value v, if it's in right subtree of parent with value p, then v > p
3. All nodes in left subtree must be less than their parent's value (exclusive)
4. All nodes in right subtree must be greater than their parent's value (exclusive)
5. Bounds are propagated correctly from root to leaves maintaining BST property

4. Data Structure Choice

For the BST validation problem, I'll use a recursive approach with explicit bounds tracking. The primary data structures needed are:

1. Primitive types for bounds tracking:

• long values for min and max bounds to handle edge cases with Integer.MAX_VALUE and Integer.MIN_VALUE
• TreeNode reference for current node traversal

2. Why each data structure is needed:

• long bounds are essential to avoid overflow issues when comparing with Integer.MAX_VALUE and Integer.MIN_VALUE
• TreeNode reference enables traversal of the tree structure without requiring additional data structures for path tracking

3. Time and space impact:

• Time complexity remains O(n) as we visit each node once
• Space complexity is O(h) where h is the height of the tree due to recursion stack (O(log n) average case, O(n) worst case for skewed trees)
• No additional data structures are needed beyond the recursive call stack

4. Helper structure considerations:

• No additional helper structures are required since we can pass bounds directly as parameters
• The approach avoids maintaining explicit collections or queues for tracking nodes

This choice keeps the solution clean and focused on the core validation logic while properly handling the edge cases that make BST validation tricky. The recursive approach with explicit bounds propagation is more intuitive than maintaining a stack of nodes and their valid ranges.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how bounds propagation works:

// Example: [5,3,8,2,4,7,9]
// Tree structure:
//       5
//      / \
//     3   8
//    / \ / \
//   2  4 7  9

// Start with root node 5, bounds (-∞, +∞)
// Process node 3 (left child of 5):
//   - Valid range: (-∞, 5) 
//   - Node value 3 is within bounds → continue
// Process node 8 (right child of 5):
//   - Valid range: (5, +∞)
//   - Node value 8 is within bounds → continue
// Process node 2 (left child of 3):
//   - Valid range: (-∞, 3)
//   - Node value 2 is within bounds → continue
// Process node 4 (right child of 3):
//   - Valid range: (3, 5)
//   - Node value 4 is within bounds → continue
// Process node 7 (left child of 8):
//   - Valid range: (5, 8)
//   - Node value 7 is within bounds → continue
// Process node 9 (right child of 8):
//   - Valid range: (8, +∞)
//   - Node value 9 is within bounds → continue

The algorithm maintains a valid range for each node based on its position in the BST. At each step:

1. We check if current node's value satisfies the bounds constraint
2. If valid, we recursively validate left and right subtrees with updated bounds:
   • For left subtree: upper bound becomes current node's value
   • For right subtree: lower bound becomes current node's value
3. The algorithm terminates when all nodes are processed or invalid bounds are detected

This approach correctly handles the BST property that for any node, all values in left subtree must be less than node value, and all values in right subtree must be greater than node value. The bounds propagate downward to maintain the constraint at every level.

The key insight is that instead of checking global min/max constraints, we maintain local bounds that get tighter as we traverse deeper into the tree.

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long minVal, long maxVal) {
        // Base case: null node is valid
        if (node == null) {
            return true;
        }
        
        // Check if current node violates BST property
        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);
    }
}

This solution uses bounds propagation to validate BST properties. For each node, we maintain the valid range of values it can have based on its ancestors. The key insight is that for any node, if we know the minimum and maximum values allowed for that node's value, we can check if the current node violates these constraints. The algorithm recursively propagates these bounds down to child nodes, ensuring that left children must be less than their parent's value and right children must be greater than their parent's value.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the binary tree. Each node is visited exactly once during the validation process, and the work done at each node (comparing values against bounds) takes constant time.

Space Complexity: O(h) where h is the height of the tree. This space is used by the recursive call stack during the depth-first traversal. In the worst case (skewed tree), h = n, making space complexity O(n). In the best case (balanced tree), h = O(log n).

The bounds propagation approach ensures that each node is processed exactly once, making the time complexity optimal. The space complexity is also optimal for a recursive solution since we must store the call stack frames.

The bounds are propagated down from parent to child nodes, maintaining the invariant that each node's value must fall within its valid range. This ensures we don't revisit or reprocess any node, making the solution linear in both time and space complexity relative to the input size.

The solution is optimal because:

1. We must examine every node at least once to validate the BST property
2. The recursive approach is necessary to maintain the bounds propagation across the tree structure
3. No additional data structures are required beyond the call stack for maintaining state

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: An empty tree is a valid BST by definition, so the solution should return true for root == null.
• Single node: A single node is always a valid BST, regardless of its value.

Duplicate Values and Repeated States

• Duplicate values: The problem typically assumes strict BST property (no duplicates). If duplicates are allowed, they must be handled consistently - either all duplicates go to the left or right subtree.
• Boundary values: When a node's value equals the min/max bound, it violates BST property (unless explicitly allowed in problem constraints).

Boundary Conditions

• Integer limits: When using Integer.MIN_VALUE or Integer.MAX_VALUE as bounds, care must be taken to avoid overflow or incorrect comparisons.
• Negative numbers: Negative values should not cause issues, but must be properly bounded.

Common Implementation Mistakes

• Incorrect bounds: Using wrong bounds (e.g., min and max swapped) or not updating them correctly when traversing left/right subtrees.
• Missing null checks: Not handling null nodes properly, leading to NullPointerExceptions.
• Incorrect comparison logic: Using <= instead of < or vice versa when checking bounds.
• Inconsistent bound propagation: Not maintaining the correct constraint that all nodes in left subtree must be less than root, and all nodes in right subtree must be greater than root.

// Example of incorrect bounds propagation:
// if (root.val <= min) return false; // Should be root.val <= min
// if (root.val >= max) return false; // Should be root.val >= max

9. Alternative Approaches

There are several alternative approaches to validating a BST, each with different trade-offs:

In-order Traversal with Previous Node Tracking: Instead of bounds propagation, we can perform an in-order traversal and ensure each node's value is strictly greater than the previously visited node. This requires storing the last visited node during traversal. The approach is intuitive but requires O(h) space for recursion stack in worst case, where h is the height of the tree.

Morris Traversal: We can avoid using explicit stack or recursion by using Morris traversal to achieve O(1) space complexity. This approach temporarily modifies the tree structure to create links back to ancestors, then restores the tree before returning. While it reduces space complexity, it's more complex to implement correctly and has higher constant factors.

Stack-based Iterative Solution: Similar to the recursive approach but using an explicit stack. This avoids recursion stack overflow for very deep trees but still requires O(h) space in worst case.

Range-based Validation with Min/Max: The bounds propagation approach is actually the most natural for this problem. While other approaches like in-order traversal are valid, they don't leverage the BST property as directly and often require more complex state tracking or tree modification.

The bounds propagation approach is preferred because it's the most direct application of BST properties, has clean implementation, and naturally handles all edge cases without requiring tree modification or complex state management. The recursive solution with bounds is optimal in both time and space complexity for this specific problem.

The stack-based iterative version trades the elegance of recursion for better control over stack space, but fundamentally follows the same logic pattern. The Morris traversal approach is more of a theoretical curiosity for this specific problem since it's not commonly needed in production code and adds significant implementation complexity.

10. Test Cases

public class BSTValidatorTestCases {
    
    // Test case 1: Valid BST
    //       5
    //      / \
    //     3   8
    //    / \ / \
    //   2  4 7  9
    @Test
    public void testValidBST() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        
        assertTrue(validateBST(root));
    }
    
    // Test case 2: Invalid BST - right child is less than root
    //       5
    //      / \
    //     3   8
    //    / \ / \
    //   2  6 7  9
    @Test
    public void testInvalidBST() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(6); // Invalid: 6 > 5 but should be < 5
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        
        assertFalse(validateBST(root));
    }
    
    // Test case 3: Edge case - single node
    @Test
    public void testSingleNode() {
        TreeNode root = new TreeNode(1);
        assertTrue(validateBST(root));
    }
    
    // Test case 4: Edge case - empty tree
    @Test
    public void testEmptyTree() {
        assertNull(validateBST(null));
    }
    
    // Test case 5: Edge case - duplicate values (invalid BST)
    //       5
    //      / \
    //     3   7
    //    / \ / \
    //   2  5 6  8
    @Test
    public void testDuplicateValues() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(5); // Invalid: duplicate value
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);
        
        assertFalse(validateBST(root));
    }
    
    // Test case 6: Edge case - negative values
    //       -5
    //      / \
    //     -8  -3
    //    / \ / \
    //  -9 -7 -4 -2
    @Test
    public void testNegativeValues() {
        TreeNode root = new TreeNode(-5);
        root.left = new TreeNode(-8);
        root.right = new TreeNode(-3);
        root.left.left = new TreeNode(-9);
        root.left.right = new TreeNode(-7);
        root.right.left = new TreeNode(-4);
        root.right.right = new TreeNode(-2);
        
        assertTrue(validateBST(root));
    }
    
    // Test case 7: Edge case - minimum and maximum integer values
    @Test
    public void testMinMaxValues() {
        TreeNode root = new TreeNode(Integer.MAX_VALUE);
        root.left = new TreeNode(Integer.MIN_VALUE);
        
        assertTrue(validateBST(root));
    }
}

11. Final Summary

The core idea is to validate a BST by maintaining and propagating valid value bounds at each node, ensuring that every node's value falls within its allowed range based on its position in the tree. This solution works because it leverages the BST property that for any node, all values in its left subtree must be less than the node's value and all values in its right subtree must be greater. The approach is efficient with O(n) time complexity and O(h) space complexity where h is the tree height, making it optimal for this validation problem. The key insight is that instead of checking individual node relationships, we maintain global constraints that cascade down the tree structure.