Java  

Validate Binary Search Tree in DSA – Rules, Algorithms, and Code

🌳 What is a Binary Search Tree (BST) in DSA.

A Binary Search Tree is a binary tree where each node follows these rules:

  1. The left subtree contains only nodes with values less than the node's value.
  2. The right subtree contains only nodes with values greater than the node's value.
  3. Both left and right subtrees must also be valid BSTs.

Example:

    5
   / \
  3   7
 / \ / \
2  4 6  8

This is a valid BST because all nodes follow the rules.

📜 Problem Statement

Given the root of a binary tree, determine whether it is a valid BST.

📏 BST Validation Rules in Detail

  1. Left Rule: Every node's value in the left subtree must be less than the root's value.
  2. Right Rule: Every node's value in the right subtree must be greater than the root's value.
  3. Recursion Rule: Apply the same rules to every subtree.
  4. Bound Tracking: Keep track of valid ranges (min and max) for each node to avoid violations deep in the tree.

🐌 Recursive Approach

We recursively check if each node's value lies within an allowed range. Initially, the range is (-∞, +∞), and it narrows as we move down the tree.

Steps:

  1. Base Case: If the node is null, return true (empty tree is valid).
  2. If the node's value is outside the current range - return false.
  3. Recursively check the left subtree with an updated max bound.
  4. Recursively check the right subtree with an updated min bound.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
}

Time Complexity: O(n)
Space Complexity: O(h) where h = height of the tree (due to recursion stack).

🔄 Iterative Approach 

We use an in-order traversal because a BST's in-order sequence must be strictly increasing.

Steps:

  1. Use a stack to perform iterative in-order traversal.
  2. Keep track of the previously visited node's value.
  3. If the current node's value is not greater than the previous value - not a BST.
public boolean isValidBSTIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    Long prev = null;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        if (prev != null && current.val <= prev) return false;
        prev = (long) current.val;
        current = current.right;
    }
    return true;
}

Time Complexity: O(n)
Space Complexity: O(h) for stack storage.

🧠 Why BST Validation is Important

  • Ensures correctness of BST-dependent operations like search and insertion.
  • Crucial in interviews to test tree traversal and recursion skills.
  • Helps in understanding range checking and traversal order.

✅ Conclusion

Validating a BST ensures that it maintains its ordered structure, allowing for efficient search, insertion, and deletion operations. By mastering both recursive and iterative methods, you build strong problem-solving skills that are applicable to many other tree-related challenges in data structures and algorithms.

 

Membership not found