Course4all
Join us on telegram
Home/dsa/Trees/Validate Binary Search Tree

Validate Binary Search Tree

Master this topic with zero to advance depth.

Validate Binary Search Tree

Is valid BST?

Medium
Approach 1

Level I: Inorder to Array

Intuition

A Binary Search Tree has a unique property: its inorder traversal (Left, Root, Right) produces a strictly increasing sequence of values. We can perform an inorder traversal, store the results in an array, and then check if the array is sorted and contains no duplicates.

Thought Process

  1. Perform DFS (Inorder).
  2. Store every node.val in a list.
  3. Iterate through the list and check if list[i] < list[i+1].
⏱ O(N)💾 O(N) (to store the array)

Detailed Dry Run

NodeLeft SubtreeRight SubtreeArray
2[1][3][1, 2, 3]
ResultValid BST!
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public boolean isValidBST(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        inorder(root, nodes);
        for (int i = 0; i < nodes.size() - 1; i++) {
            if (nodes.get(i) >= nodes.get(i + 1)) return false;
        }
        return true;
    }

    private void inorder(TreeNode node, List<Integer> nodes) {
        if (node == null) return;
        inorder(node.left, nodes);
        nodes.add(node.val);
        inorder(node.right, nodes);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(new Main().isValidBST(root)); // true
    }
}
Approach 2

Level II: Iterative Inorder (Stack)

Intuition

Using a stack, we can simulate the recursion of an inorder traversal. We push all left children of the current node onto the stack, then pop one, check it, and move to its right child.

Logic

Keep a pointer prev to the previously visited node. At each step, if current.val <= prev.val, it's not a valid BST.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [2, 1]. Pop 1, prev=1. Pop 2, prev=2 (2>1 OK). Push 3, Pop 3, prev=3 (3>2 OK).

java
public class Main {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (prev != null && root.val <= prev.val) return false;
            prev = root;
            root = root.right;
        }
        return true;
    }
}
Approach 3

Level III: Optimal (Recursive Bounds)

Intuition

Thought Process

Instead of storing the whole tree in an array, we can validate each node as we visit it by passing down an allowable range (min, max). 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.

Pattern

Top-Down DFS: Pass constraints from parent to children.

Diagram

10 (range: -∞, +∞) / \ 5 15 / \ / \ L R L R (5 range: -∞, 10) (15 range: 10, +∞)
⏱ O(N) (visiting each node once)💾 O(H) (recursion depth equal to tree height)

Detailed Dry Run

NodeRange (Min, Max)Valid?
10(-∞, +∞)YES
5(-∞, 10)YES
15(10, +∞)YES
java
public class Main {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }

    private boolean validate(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
}

⚠️ Common Pitfalls & Tips

Be careful with Integer.MIN_VALUE. Use null or Long for the initial bounds to handle nodes that contain the minimum possible integer value.

← Previous QuestionConstruct Binary Tree from Preorder and Inorder Traversal
Next Question →Binary Tree Level Order Traversal