Validate Binary Search Tree Algorithm Solution

Validating whether a binary tree satisfies the properties of a valid Binary Search Tree is a classic algorithm problem that tests understanding of tree traversal and boundary condition checking in software engineering interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input tree be mutated during validation, or should we preserve the original structure?
2. What is the expected range of node values (e.g., are there constraints on min/max values)?
3. Should we handle duplicate values in the tree, and if so, how should they be treated?
4. What is the maximum expected size of the tree (e.g., number of nodes)?
5. Should we return a boolean or throw an exception for invalid trees?

Restated problem:
Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST). A valid BST must satisfy that 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 than the node's value.

Input/Output specification:

• Input: Root node of a binary tree (TreeNode type)
• Output: Boolean indicating whether the tree is a valid BST

Constraints:

• Number of nodes in the tree: [1, 10⁴]
• Node values can be in range [-2³¹, 2³¹ - 1]
• Duplicates are not allowed in a valid BST (strict inequality required)

Assumptions:

• The tree is a valid binary tree structure (each node has at most two children)
• Node values are integers within the standard 32-bit signed integer range
• The tree is not necessarily balanced

Data shape and hidden structure:
The problem involves a hierarchical data structure where each node has an ordering constraint relative to its ancestors. The key insight is that the validation isn't just about immediate children but about maintaining a global constraint across the entire tree. This suggests that we need to track bounds (min and max values) as we traverse the tree, ensuring each node's value lies within the valid range determined by its ancestors.

This is a classic BST validation problem that tests understanding of tree traversal, constraint propagation, and the subtle distinction between local and global validity conditions.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is Range-based Validation or Boundary Checking. This problem fits the BST validation pattern where each node must satisfy specific constraints based on its position in the tree.

Wording that signals the pattern

The key phrases are:

• "validate" - indicates we need to check if a tree satisfies BST properties
• "binary search tree" - signals the fundamental property that for any node, all values in left subtree are less than the node value, and all values in right subtree are greater
• "valid" - suggests we're checking constraints rather than building or modifying

Why this problem fits that pattern

This is fundamentally about constraint propagation through the tree structure. Each node must be within a valid range determined by its ancestors - this creates a recursive constraint validation problem where:

• Left child must be within (min, parent_value)
• Right child must be within (parent_value, max)

Core insight needed to solve it

The key insight is that validating a BST requires maintaining bounds as we traverse the tree. Each node's value must be strictly within a valid range that's determined by all its ancestors. This is not just about comparing with immediate parent, but maintaining the global constraint that follows from the entire path to root.

This pattern appears in many tree validation problems where we must ensure that constraints propagate correctly through the tree structure, making it a classic example of recursive constraint validation or bounded tree traversal.

3. Approach Evolution

Interview communication script:

My first instinct is to check if each node satisfies the BST property relative to its ancestors, but that would require checking all ancestors for every node, making it O(n²) in worst case. Let me think about how to optimize this.

I notice that instead of checking all ancestors, I can maintain bounds for each node - every node must fall within a valid range determined by its parent and grandparents. If I maintain an upper and lower bound for each node, I can validate it in O(n) time.

The key insight is that when traversing left, the upper bound becomes the parent's value, and when traversing right, the lower bound becomes the parent's value. This way I don't need to check all ancestors - just the immediate bounds.

Let me trace through this approach:

• For root node, there are no bounds (or bounds are negative infinity to positive infinity)
• When going left from a node with value 10, the new upper bound becomes 10
• When going right from a node with value 10, the new lower bound becomes 10
• This creates a clean recursive structure where each node is validated against its valid range

This approach is optimal because:

1. Each node is visited exactly once - O(n) time complexity
2. We only need to store the current bounds - O(h) space where h is height (O(log n) average, O(n) worst case)
3. We don't need to collect all values first and then sort or compare - we validate during traversal

Brute-force approach: The naive approach would be to collect all node values in an array, sort them, and verify that the in-order traversal produces a strictly increasing sequence. This is O(n log n) time and O(n) space, which is inefficient because:

• We're doing unnecessary sorting
• We're storing all values when we only need to validate the BST property during traversal

Improved approach: The key optimization is to realize that we don't need to collect all values - we can validate the BST property in-place during traversal. For each node, we check if its value lies within a valid range (lower bound and upper bound) that's determined by the path from root to that node.

Final approach with step-by-step reasoning:

1. Start with root node and no bounds (or infinite bounds)
2. For each node, check if its value is within the valid range [minVal, maxVal]
3. If valid, recursively validate left subtree with updated upper bound (parent's value) and right subtree with updated lower bound (parent's value)
4. Base case: null nodes are valid BSTs
5. Invariant maintained: every node in left subtree is less than parent, every node in right subtree is greater than parent

Important invariants that must hold:

• For any node, its value must be strictly greater than lower bound and strictly less than upper bound
• When moving left, the new upper bound is the parent's value (exclusive)
• When moving right, the new lower bound is the parent's value (exclusive)
• The bounds properly capture the constraints from all ancestors in the path

4. Data Structure Choice

For validating a binary search tree, I need to carefully consider the data structures that will support my validation approach.

The primary data structure is the TreeNode class itself, which represents the binary tree nodes. Each node contains:

• An integer value (val)
• References to left and right child nodes (left, right)

I don't need any additional data structures for the core validation logic when using the optimal approach. The key insight is that I can validate each node against a range of valid values rather than storing all previously seen values.

However, I do need to maintain bounds during traversal:

• minVal - the minimum valid value for current node
• maxVal - the maximum valid value for current node

These bounds are not stored in a separate data structure but are passed as parameters during recursive calls. This approach avoids the need for:

• A stack or queue for iterative traversal (though I could implement an iterative solution with explicit stack)
• A HashSet or other collection to store visited values

The choice of using parameter passing for bounds instead of maintaining a separate data structure is optimal because:

1. It uses O(1) extra space for the bounds (not counting recursion stack)
2. It avoids the overhead of creating additional collections
3. It naturally expresses the constraint validation logic

The recursive call stack is the only additional space used, which is necessary for the traversal and represents the natural space complexity of the recursive approach.

For the iterative alternative, I would use a stack with pairs containing nodes and their valid value ranges, but that's not the chosen approach here.

The solution uses only the standard TreeNode structure with minimal additional state tracking through parameter passing, making it clean and efficient.

5. Algorithm Walkthrough

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

Example: [5,3,8,null,null,6,9] representing a valid BST

Step 1: Start with root node 5, no bounds initially

• Call validate(5, null, null)
• Current node = 5, min = null, max = null
• Check: null < 5 < null → True (no bounds to check)
• Recursively validate left subtree with validate(3, null, 5)
• Recursively validate right subtree with validate(8, 5, null)

Step 2: Validate left subtree (node 3)

• Call validate(3, null, 5)
• Current node = 3, min = null, max = 5
• Check: null < 3 < 5 → True (3 is within bounds)
• Recursively validate left subtree with validate(null, null, 3) → returns true
• Recursively validate right subtree with validate(null, 3, 5) → returns true

Step 3: Validate right subtree (node 8)

• Call validate(8, 5, null)
• Current node = 8, min = 5, max = null
• Check: 5 < 8 < null → True (8 is within bounds)
• Recursively validate left subtree with validate(6, 8, null) → returns true
• Recursively validate right subtree with validate(9, 8, null) → returns true

Step 4: Validate node 6 (in left subtree of 8)

• Call validate(6, 5, 8)
• Current node = 6, min = 5, max = 8
• Check: 5 < 6 < 8 → True (6 is within bounds)
• Both children are null, return true

Step 5: Validate node 9 (in right subtree of 8)

• Call validate(9, 8, null)
• Current node = 9, min = 8, max = null
• Check: 8 < 9 < null → True (9 is within bounds)
• Both children are null, return true

Final Result: All validations pass → returns true

The algorithm maintains the invariant that each node's value must be strictly between its valid min and max bounds, ensuring BST property is preserved throughout the tree traversal. The recursion naturally handles the constraint propagation from parent to child nodes.

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer min, Integer max) {
    // Base case: null node is valid
    if (node == null) return true;
    
    // Check current node against bounds
    if ((min != null && node.val <= min) || 
        (max != null && node.val >= max)) {
        return false;
    }
    
    // Recursively validate left and right subtrees with updated bounds
    return validate(node.left, min, node.val) && 
           validate(node.right, node.val, max);
}

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 the key insight that each node must fall within a valid range determined by its ancestors. Rather than just checking immediate parent-child relationships, we maintain the global constraints that every node in the left subtree must be less than the current node's value, and every node in the right subtree must be greater than the current node's value. Using long instead of int prevents overflow issues when dealing with the extreme values.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm visits each node exactly once in a single traversal. At each node, we perform O(1) work to validate the current node against its bounds and update the bounds for children. Since we process each of the n nodes once, the total time complexity is O(n).

Space Complexity: O(h) where h is the height of the tree

The space complexity comes from the recursion stack. In the worst case (skewed tree), the recursion depth can be O(n) when the tree is essentially a linked list. In the best case (balanced tree), the recursion depth is O(log n). Therefore, space complexity is O(h) where h is the height of the tree.

Why these bounds are correct:

• Time: Each node is visited exactly once, and all operations at each node are constant time. There's no redundant computation or nested loops that would increase the time complexity beyond linear.

• Space: The maximum recursion depth corresponds to the longest path from root to leaf. For a balanced binary tree, this is O(log n), while for a skewed tree, it's O(n). The algorithm does not use any additional data structures that scale with input size beyond the recursion stack.

Optimality:

This solution is optimal for the problem as stated. We must examine each node at least once to validate that it satisfies the BST property, making O(n) time complexity unavoidable. The space complexity is optimal for a recursive approach with respect to the tree's height, as we cannot avoid the recursion stack overhead.

The solution achieves the best possible trade-off between time and space complexity for this validation problem, with no room for improvement in either dimension.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: An empty tree is a valid BST by definition, so we must handle root == null correctly
• Single node: A single node is always a valid BST, but we must ensure our bounds checking works properly for this case

Duplicate Values and Repeated States

• Duplicate values: The problem requires strict BST property where left < root < right. Duplicates are not allowed in a valid BST, so we must ensure our bounds properly exclude equal values
• Boundary duplicates: When a node value equals the minimum/maximum bound, it's invalid (e.g., if we're checking that a node must be > 10, and the node value is exactly 10, it's invalid)

Boundary Conditions

• Integer limits: The problem involves integer values, so we must be careful with Integer.MIN_VALUE and Integer.MAX_VALUE. A node with value Integer.MIN_VALUE cannot have a left child, and a node with value Integer.MAX_VALUE cannot have a right child
• Extreme values: When the tree contains nodes with extreme integer values, we must ensure our bounds propagation correctly handles these edge cases

Common Implementation Mistakes

• Incorrect bounds: Using <= instead of < when checking bounds, or incorrectly passing bounds to recursive calls
• Wrong bound propagation: Not properly updating min/max constraints when traversing left/right subtrees (e.g., passing min instead of max to left subtree)
• Missing null checks: Not handling null nodes properly in recursive calls, leading to NullPointerException
• Overlapping bounds: Setting bounds too restrictively or not allowing proper range propagation

Implementation-specific Issues

• Integer overflow: When computing bounds with extreme values, we must be careful about integer overflow in our comparisons
• Inconsistent state management: Not maintaining proper state of valid ranges throughout the traversal

// Example problematic case:
//       5
//      / \
//     4   6
//        / \
//       3   7
// 
// If we don't properly bound the left subtree of 6, we might incorrectly allow 3
// to be valid when it should be rejected because it's less than or equal to 5

9. Alternative Approaches

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

In-order Traversal with Array: Instead of using a global variable to track the previous value, we can collect all values in an in-order traversal into an array and then check if the array is strictly increasing. This approach has O(n) space complexity due to storing all values, but the logic is simpler to understand and implement. However, it requires two passes through the tree.

Morris Traversal: We can use Morris traversal to achieve O(1) space complexity without recursion. This approach temporarily modifies the tree structure by creating links to predecessors, then restores the tree before finishing. It's memory-efficient but more complex to implement correctly and can be harder to debug.

Range-based Validation: Rather than tracking just the previous value, we can maintain valid ranges for each node. For any node, if its value falls within the valid range (min, max), we recursively validate its left and right subtrees with updated ranges. This approach is conceptually clean but requires careful handling of the range bounds.

Stack-based Iterative Approach: Using an explicit stack to simulate the recursive in-order traversal. This avoids recursion overhead but requires O(h) space where h is the tree height, similar to our chosen solution's space complexity.

The key trade-off among these alternatives is between code clarity, space efficiency, and implementation complexity. Our chosen solution strikes a good balance by being clean, efficient, and easy to understand while maintaining optimal O(h) space complexity where h is the tree height.

10. Test Cases

// Test case 1: Valid BST
//       5
//      / \
//     3   8
//    / \ / \
//   2  4 7  9
TreeNode root1 = new TreeNode(5);
root1.left = new TreeNode(3);
root1.right = new TreeNode(8);
root1.left.left = new TreeNode(2);
root1.left.right = new TreeNode(4);
root1.right.left = new TreeNode(7);
root1.right.right = new TreeNode(9);
// Expected: true

// Test case 2: Invalid BST - right child too small
//       5
//      / \
//     3   8
//    / \ / \
//   2  6 7  9  (6 > 5, violates BST property)
TreeNode root2 = new TreeNode(5);
root2.left = new TreeNode(3);
root2.right = new TreeNode(8);
root2.left.left = new TreeNode(2);
root2.left.right = new TreeNode(6); // Invalid: 6 > 5
root2.right.left = new TreeNode(7);
root2.right.right = new TreeNode(9);
// Expected: false

// Test case 3: Single node
TreeNode root3 = new TreeNode(1);
// Expected: true

// Test case 4: Empty tree
TreeNode root4 = null;
// Expected: true

// Test case 5: Duplicate values - invalid BST
//       5
//      / \
//     3   5  (duplicate value)
TreeNode root5 = new TreeNode(5);
root5.left = new TreeNode(3);
root5.right = new TreeNode(5);
// Expected: false

// Test case 6: Large values - edge case with Integer.MAX_VALUE
TreeNode root6 = new TreeNode(Integer.MAX_VALUE);
root6.left = new TreeNode(Integer.MAX_VALUE - 1);
// Expected: true

The test cases cover:

• Valid BST structure with proper ordering
• Invalid BST due to violation of BST property (right subtree contains smaller value)
• Edge cases with single node and empty tree
• Duplicate values that violate BST constraints
• Boundary conditions with maximum integer values

Each test case validates different aspects of the BST validation logic, ensuring proper handling of various tree configurations and edge conditions.

11. Final Summary

The core insight is that a valid BST requires each node to fall within a specific range of valid values determined by its ancestors, which we maintain using a bounds-based validation approach. This solution works efficiently by avoiding the need to store all values in memory and instead validating each node against its immediate constraints. The O(n) time complexity is optimal since we must examine each node at least once, and the O(h) space complexity is necessary due to the recursion stack depth in the worst case. This approach elegantly handles all edge cases including duplicate values and empty trees while maintaining clean, readable code structure.