Validate Binary Search Tree

Given a binary tree, containing unique values, determine if it is a valid binary search tree.

Note: The invariants of a binary search tree (in our case) are:

All values to the left of a given node are less than the current node's value
All values to the right of a given node are greater than the current node's value
Both the left and right subtrees of a given node must also be binary search trees

Example(s)

Example 1:

Input:
   1
 /   \
2     3

Output: false
Explanation:
Node 1 has value 1
Left child has value 2, which is greater than 1
This violates the BST property (left should be less)

Example 2:

Input:
   2
 /   \
1     3

Output: true
Explanation:
Node 2 has value 2
Left child (1) < 2 ✓
Right child (3) > 2 ✓
Both subtrees are valid BSTs

Example 3:

Input:
    5
   / \
  1   4
     / \
    3   6

Output: false
Explanation:
Node 5 has value 5
Right child 4 < 5 ✗ (should be greater)
This violates the BST property

Example 4:

Input:
    10
   /  \
  5   15
     /  \
    6   20

Output: false
Explanation:
Node 10 has value 10
Right subtree: 15 is valid
But 15's left child is 6, which is less than 10 (ancestor)
This violates the BST property (all right descendants must be > 10)

Solution

The solution uses DFS with Bounds Checking:

Bounds tracking: For each node, track min and max allowed values
Recursive validation: Check if node value is within bounds
Update bounds: For left subtree, update max; for right subtree, update min
Base case: Null nodes are valid BSTs

JavaScript Solution
Python Solution

JavaScript Solution - DFS with Bounds

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Check if binary tree is a valid BST
* @param {TreeNode} root - Root of binary tree
* @return {boolean} - Whether tree is a valid BST
*/
function isValidBST(root) {
/**
 * Helper function to validate with bounds
 * @param {TreeNode} node - Current node
 * @param {number} min - Minimum allowed value
 * @param {number} max - Maximum allowed value
 * @return {boolean} - Whether subtree is valid BST
 */
function validate(node, min, max) {
  // Base case: null nodes are valid
  if (!node) return true;
  
  // Check if current node value is within bounds
  if (node.val <= min || node.val >= max) {
    return false;
  }
  
  // Recursively validate left and right subtrees
  // Left subtree: all values must be < node.val, so max = node.val
  // Right subtree: all values must be > node.val, so min = node.val
  return validate(node.left, min, node.val) && 
         validate(node.right, node.val, max);
}

// Start with unbounded range (use Infinity for bounds)
return validate(root, -Infinity, Infinity);
}

// Helper function to create tree nodes for testing
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

// Test cases
// Example 1: [1, 2, 3]
const tree1 = new TreeNode(1,
new TreeNode(2),
new TreeNode(3)
);
console.log('Example 1:', isValidBST(tree1)); // false

// Example 2: [2, 1, 3]
const tree2 = new TreeNode(2,
new TreeNode(1),
new TreeNode(3)
);
console.log('Example 2:', isValidBST(tree2)); // true

// Example 3: [5, 1, 4, null, null, 3, 6]
const tree3 = new TreeNode(5,
new TreeNode(1),
new TreeNode(4, new TreeNode(3), new TreeNode(6))
);
console.log('Example 3:', isValidBST(tree3)); // false

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - DFS with Bounds

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

def is_valid_bst(root: Optional[TreeNode]) -> bool:
  """
  Check if binary tree is a valid BST
  
  Args:
      root: Root of binary tree
      
  Returns:
      bool: Whether tree is a valid BST
  """
  def validate(node: Optional[TreeNode], min_val: float, max_val: float) -> bool:
      """
      Helper function to validate with bounds
      
      Args:
          node: Current node
          min_val: Minimum allowed value
          max_val: Maximum allowed value
          
      Returns:
          bool: Whether subtree is valid BST
      """
      # Base case: null nodes are valid
      if not node:
          return True
      
      # Check if current node value is within bounds
      if node.val <= min_val or node.val >= max_val:
          return False
      
      # Recursively validate left and right subtrees
      # Left subtree: all values must be < node.val, so max = node.val
      # Right subtree: all values must be > node.val, so min = node.val
      return validate(node.left, min_val, node.val) and              validate(node.right, node.val, max_val)
  
  # Start with unbounded range (use float('inf') for bounds)
  return validate(root, float('-inf'), float('inf'))

# Helper class for testing
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

# Test cases
# Example 1: [1, 2, 3]
tree1 = TreeNode(1,
  TreeNode(2),
  TreeNode(3)
)
print('Example 1:', is_valid_bst(tree1))  # False

# Example 2: [2, 1, 3]
tree2 = TreeNode(2,
  TreeNode(1),
  TreeNode(3)
)
print('Example 2:', is_valid_bst(tree2))  # True

# Example 3: [5, 1, 4, None, None, 3, 6]
tree3 = TreeNode(5,
  TreeNode(1),
  TreeNode(4, TreeNode(3), TreeNode(6))
)
print('Example 3:', is_valid_bst(tree3))  # False

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (In-Order Traversal)

Here's an alternative using in-order traversal (BST in-order gives sorted order):

JavaScript In-Order
Python In-Order

/**
 * Alternative: In-order traversal
 * BST in-order traversal gives sorted order
 */
function isValidBSTInOrder(root) {
  let prev = null;
  
  function inOrder(node) {
    if (!node) return true;
    
    // Traverse left subtree
    if (!inOrder(node.left)) return false;
    
    // Check current node
    if (prev !== null && node.val <= prev) {
      return false;
    }
    prev = node.val;
    
    // Traverse right subtree
    return inOrder(node.right);
  }
  
  return inOrder(root);
}

def is_valid_bst_inorder(root: Optional[TreeNode]) -> bool:
    """
    Alternative: In-order traversal
    BST in-order traversal gives sorted order
    """
    prev = None
    
    def in_order(node: Optional[TreeNode]) -> bool:
        nonlocal prev
        
        if not node:
            return True
        
        # Traverse left subtree
        if not in_order(node.left):
            return False
        
        # Check current node
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        
        # Traverse right subtree
        return in_order(node.right)
    
    return in_order(root)

Complexity

Time Complexity: O(n) - Where n is the number of nodes in the tree. We visit each node once.
Space Complexity: O(h) - Where h is the height of the tree. For the recursion stack. In worst case (skewed tree), O(n). In average case (balanced tree), O(log n).

Approach

The solution uses DFS with Bounds Checking:

Bounds tracking:
- For each node, maintain min and max allowed values
- Initially, use -Infinity and Infinity (unbounded)
Validation check:
- Current node value must be: min < node.val < max
- If not, return false (violates BST property)
Recursive validation:
- Left subtree: All values must be < current node
  - Update max bound to node.val
  - Keep min bound unchanged
- Right subtree: All values must be > current node
  - Update min bound to node.val
  - Keep max bound unchanged
Base case:
- Null nodes are valid BSTs (empty tree is valid)

Key Insights

Bounds checking: Track min and max allowed values for each node
BST property: Left < node < right, recursively
Ancestor constraint: All descendants must satisfy ancestor bounds
O(n) time: Must visit all nodes
O(h) space: Recursion stack depth

Step-by-Step Example

Let's trace through Example 1:

Tree:
   1
 /   \
2     3

isValidBST(root=1):
  validate(1, -Infinity, Infinity):
    node.val=1, min=-Infinity, max=Infinity
    Check: -Infinity < 1 < Infinity ✓
    validate(2, -Infinity, 1):
      node.val=2, min=-Infinity, max=1
      Check: -Infinity < 2 < 1 ✗ (2 >= 1)
      Return false ✗
    Return false

Result: false

Let's trace through Example 2:

Tree:
   2
 /   \
1     3

isValidBST(root=2):
  validate(2, -Infinity, Infinity):
    node.val=2, min=-Infinity, max=Infinity
    Check: -Infinity < 2 < Infinity ✓
    validate(1, -Infinity, 2):
      node.val=1, min=-Infinity, max=2
      Check: -Infinity < 1 < 2 ✓
      validate(null, -Infinity, 1) → true
      validate(null, 1, 2) → true
      Return true ✓
    validate(3, 2, Infinity):
      node.val=3, min=2, max=Infinity
      Check: 2 < 3 < Infinity ✓
      validate(null, 2, 3) → true
      validate(null, 3, Infinity) → true
      Return true ✓
    Return true && true = true ✓

Result: true

Visual Representation

Example 1: Not a BST
   1
 /   \
2     3

Validation:
  Node 1: (-∞, +∞) → 1 is valid ✓
  Node 2: (-∞, 1) → 2 >= 1 ✗
  Result: false ✗

Example 2: Valid BST
   2
 /   \
1     3

Validation:
  Node 2: (-∞, +∞) → 2 is valid ✓
  Node 1: (-∞, 2) → 1 < 2 ✓
  Node 3: (2, +∞) → 3 > 2 ✓
  Result: true ✓

Example 4: Not a BST
    10
   /  \
  5   15
     /  \
    6   20

Validation:
  Node 10: (-∞, +∞) → 10 is valid ✓
  Node 5: (-∞, 10) → 5 < 10 ✓
  Node 15: (10, +∞) → 15 > 10 ✓
  Node 6: (10, 15) → 6 <= 10 ✗ (should be > 10)
  Result: false ✗

Edge Cases

Empty tree: Return true (empty tree is valid BST)
Single node: Return true (single node is valid BST)
All left children: Must be decreasing
All right children: Must be increasing
Large values: Use Infinity for bounds

Important Notes

Strict inequality: Left < node < right (not <= or >=)
Bounds propagation: Bounds are inherited from ancestors
Ancestor constraint: All descendants must satisfy all ancestor bounds
O(n) time: Must visit all nodes
O(h) space: Recursion stack depth

Why Bounds Checking Works

Key insight:

A BST must satisfy: left < node < right
But this is not enough! We also need:
- All left descendants < node
- All right descendants > node
- All descendants must satisfy ancestor bounds
Bounds checking ensures all these constraints are satisfied

Example:

Tree: 10 → 15 → 6
Node 6 is in right subtree of 10, so must be > 10
But 6 < 10, so invalid
Bounds checking catches this: node 6 has bounds (10, 15), but 6 <= 10

Search in BST: Search in valid BST
Insert into BST: Insert maintaining BST property
Delete Node in BST: Delete maintaining BST property
Kth Smallest Element in BST: Use BST property

Takeaways

Bounds checking ensures all BST constraints
Ancestor bounds must be satisfied by all descendants
O(n) time to visit all nodes
O(h) space for recursion stack
Classic tree problem with important constraints

Example(s)​

Solution​

JavaScript Solution - DFS with Bounds

Output:

Python Solution - DFS with Bounds

Output:

Alternative Solution (In-Order Traversal)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why Bounds Checking Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (In-Order Traversal)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why Bounds Checking Works

Related Problems

Takeaways