Skip to main content
CodePeetCodePeet
CodePeet 250

Validate Binary Search Tree

MEDIUMProblemSolveExternal Links

Description

Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).

A valid BST satisfies the following rules:

  • The left subtree of every node contains only nodes whose values are strictly less than the node's value.
  • The right subtree of every node contains only nodes whose values are strictly greater than the node's value.
  • Both the left and right subtrees must themselves be valid BSTs.

Note that a BST does not allow duplicate values. Every node's value must be unique within its subtree constraints.

Two binary trees side by side: a valid BST [2,1,3] and an invalid BST [5,1,4,null,null,3,6] with the violation highlighted
Two binary trees side by side: a valid BST [2,1,3] and an invalid BST [5,1,4,null,null,3,6] with the violation highlighted

Examples

Example 1

Input: root = [2, 1, 3]

Output: true

Explanation: The root node is 2. Its left child is 1, which is less than 2 — valid. Its right child is 3, which is greater than 2 — valid. Both children are leaf nodes (trivially valid BSTs). Since every node satisfies the BST property, the tree is a valid BST.

Example 2

Input: root = [5, 1, 4, null, null, 3, 6]

Output: false

Explanation: The root is 5. Its left child is 1 (less than 5 — fine). Its right child is 4. However, 4 is less than 5, which violates the BST rule that all right-subtree values must be strictly greater than the node's value. Therefore, this tree is not a valid BST.

Example 3

Input: root = [5, 4, 6, null, null, 3, 7]

Output: false

Explanation: The root is 5. The right subtree is rooted at 6 with children 3 and 7. While 6 > 5 is fine at the immediate level, node 3 is in the right subtree of 5 but has value 3 < 5. This violates the BST property — every node in the right subtree of 5 must be greater than 5. Simply checking immediate parent-child relationships is not enough; we must validate against all ancestors.

Constraints

  • 1 ≤ Number of nodes ≤ 10^4
  • -2^31 ≤ Node.val ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward way to check if a binary tree is a valid BST is to perform an inorder traversal and collect all node values into an array. A fundamental property of a BST is that its inorder traversal always produces values in strictly ascending order. If the resulting array is sorted in strictly increasing order, the tree is a valid BST; otherwise, it is not.

Think of it like reading a bookshelf from left to right. If the books are arranged by increasing page number, the shelf is sorted. If at any point you find a book with fewer pages than the one before it, the arrangement is broken.

Step-by-Step Explanation

Let's trace through with the tree [5, 1, 4, null, null, 3, 6] (Example 2):

The tree looks like:

      5
     / \
    1   4
       / \
      3   6

Step 1: Start the inorder traversal. Go to the leftmost node.

  • Visit node 1 (leaf, no left child). Add 1 to the result array.
  • Result: [1]

Step 2: Backtrack to root node 5. Add 5 to the result array.

  • Result: [1, 5]

Step 3: Move to the right subtree of 5. Go to node 4, then its left child 3.

  • Visit node 3 (leaf). Add 3 to the result array.
  • Result: [1, 5, 3]

Step 4: Backtrack to node 4. Add 4 to the result array.

  • Result: [1, 5, 3, 4]

Step 5: Move to node 6 (right child of 4). Add 6 to the result array.

  • Result: [1, 5, 3, 4, 6]

Step 6: Check if the result array is strictly increasing.

  • Compare consecutive pairs: 1 < 5 ✓, but 5 > 3 ✗
  • The array is NOT sorted. The tree is NOT a valid BST.

Result: Return false.

Brute Force — Inorder Traversal to Array — Watch the inorder traversal collect values into an array, then detect the violation where 5 is followed by 3.

Algorithm

  1. Perform an inorder traversal of the binary tree (left → root → right)
  2. Collect all node values into an array
  3. Iterate through the array and check if each element is strictly less than the next element
  4. If any element is greater than or equal to its successor, return false
  5. If the entire array is strictly increasing, return true

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& values) {
        if (!root) return;
        inorder(root->left, values);
        values.push_back(root->val);
        inorder(root->right, values);
    }
    
    bool isValidBST(TreeNode* root) {
        vector<int> values;
        inorder(root, values);
        
        for (int i = 1; i < values.size(); i++) {
            if (values[i] <= values[i - 1]) {
                return false;
            }
        }
        return true;
    }
};
# 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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        values = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)
        
        inorder(root)
        
        for i in range(1, len(values)):
            if values[i] <= values[i - 1]:
                return False
        return True
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { this.val = val; }
 * }
 */
class Solution {
    private List<Integer> values = new ArrayList<>();
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        values.add(root.val);
        inorder(root.right);
    }
    
    public boolean isValidBST(TreeNode root) {
        inorder(root);
        
        for (int i = 1; i < values.size(); i++) {
            if (values.get(i) <= values.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once during the inorder traversal, and then iterate through the resulting array of n elements once to check sorting. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node values in an array. Additionally, the recursion stack uses O(h) space where h is the height of the tree (O(n) in the worst case for a skewed tree, O(log n) for a balanced tree). The dominant term is the O(n) array storage.

Why This Approach Is Not Efficient

While the brute force approach is O(n) in time, it uses O(n) extra space to store the entire inorder traversal in an array. For large trees with up to 10^4 nodes, this is manageable, but we are doing unnecessary work:

  1. Extra space for the array: We store all n values even though we only need to compare consecutive pairs. We do not need to remember the entire sequence — just the previous value.
  2. Two-pass approach: We first traverse the entire tree to build the array, then scan the array again to check ordering. We could detect violations during the traversal itself and stop early.

The key insight is: instead of collecting all values and then checking, we can check the BST property during the traversal by keeping track of just the previously visited value. This eliminates the O(n) array and reduces the approach to a single pass.

Better Approach - Inorder Traversal with Previous Pointer

Intuition

We can improve the brute force by eliminating the array entirely. Instead of storing all inorder values and then checking, we maintain a single variable that tracks the last node we visited during the inorder traversal. At each node, we simply compare: is the current node's value strictly greater than the previous node's value?

If at any point the current value is less than or equal to the previous value, we know the BST property is violated and can immediately return false without traversing the rest of the tree.

Imagine walking through a library where books should be arranged by ascending ID. Instead of writing down every ID and checking the list afterward, you just remember the last book's ID. Each time you pick up a new book, you compare it with the one you just put down. The moment you find a book with a smaller ID, you know the arrangement is wrong.

Step-by-Step Explanation

Let's trace through the valid BST [2, 1, 3] (Example 1):

The tree looks like:

    2
   / \
  1   3

Step 1: Initialize prev = null (no previous node yet). Start inorder from root 2.

Step 2: Go left to node 1. Node 1 has no left child, so visit it.

  • prev is null, so no comparison needed (first node is always valid).
  • Set prev = 1.

Step 3: Backtrack to node 2. Visit root 2.

  • Compare: 2 > prev (1)? Yes ✓. The current value is strictly greater.
  • Set prev = 2.

Step 4: Go right to node 3. Visit node 3.

  • Compare: 3 > prev (2)? Yes ✓. Still strictly increasing.
  • Set prev = 3.

Step 5: No more nodes to visit. All comparisons passed.

Result: Return true. The tree is a valid BST.

Inorder with Previous Pointer — Validating [2, 1, 3] — Watch how we track just the previous value during inorder traversal, comparing each node to ensure strictly increasing order.

Algorithm

  1. Initialize a variable prev to track the value of the last visited node (start with negative infinity or null)
  2. Perform an inorder traversal (left → root → right):
    a. Recursively traverse the left subtree. If it returns false, propagate false.
    b. At the current node, compare its value with prev:
    • If current value ≤ prev, return false (BST violation)
    • Otherwise, update prev to the current value
      c. Recursively traverse the right subtree. If it returns false, propagate false.
  3. If all nodes pass the check, return true

Code

class Solution {
public:
    TreeNode* prev = nullptr;
    
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        
        // Check left subtree
        if (!isValidBST(root->left)) return false;
        
        // Check current node against previous
        if (prev && root->val <= prev->val) return false;
        prev = root;
        
        // Check right subtree
        return isValidBST(root->right);
    }
};
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        
        def inorder(node):
            if not node:
                return True
            
            # Check left subtree
            if not inorder(node.left):
                return False
            
            # Check current node against previous
            if self.prev is not None and node.val <= self.prev:
                return False
            self.prev = node.val
            
            # Check right subtree
            return inorder(node.right)
        
        return inorder(root)
class Solution {
    private TreeNode prev = null;
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        
        // Check left subtree
        if (!isValidBST(root.left)) return false;
        
        // Check current node against previous
        if (prev != null && root.val <= prev.val) return false;
        prev = root;
        
        // Check right subtree
        return isValidBST(root.right);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once during the inorder traversal. Each visit involves a constant-time comparison and update. In the worst case, we traverse all n nodes. In the best case, we may detect a violation early and return false before visiting all nodes.

Space Complexity: O(h)

We no longer store all values in an array. The only space used is the recursion call stack, which is proportional to the height h of the tree. For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n). We also use O(1) extra space for the prev variable.

Why This Approach Is Not Efficient

The inorder traversal with a previous pointer is already O(n) time and O(h) space, which is quite efficient. However, it has a conceptual limitation:

  1. Inorder-specific: The approach relies on the specific property that inorder traversal of a BST produces sorted output. While correct, it does not directly encode the BST constraint at each node — it validates the property indirectly through traversal order.
  2. Not easily generalizable: If the problem changes slightly (e.g., validate a BST with duplicates allowed on one side), the inorder approach needs careful modification.

A more direct and elegant approach exists: passing down explicit valid ranges (minimum and maximum bounds) to each node. This approach directly captures the BST definition — each node must fall within a valid range defined by its ancestors. It is equally efficient in time and space but is conceptually clearer, more generalizable, and easier to reason about for edge cases involving extreme values.

Optimal Approach - Min/Max Range Validation

Intuition

The BST property says: every node in the left subtree must be less than the current node, and every node in the right subtree must be greater. But this constraint is not just about the immediate parent — it is about ALL ancestors.

Consider node 3 in the tree [5, 1, 4, null, null, 3, 6]. Node 3 is the left child of 4, so 3 < 4 is fine. But node 3 is also in the right subtree of the root 5, so it must satisfy 3 > 5 — which it does not.

The insight is to pass down a valid range [low, high] as we recurse. The root can be any value, so its range is (-∞, +∞). When we go left from a node with value V, the new upper bound becomes V (all left descendants must be < V). When we go right, the new lower bound becomes V (all right descendants must be > V).

Think of it like a hallway with shrinking walls. At the entrance, the walls are infinitely far apart. Each time you turn left, the right wall moves closer. Each time you turn right, the left wall moves closer. If at any point you find yourself squeezed between walls that have crossed, you know the path is invalid.

Step-by-Step Explanation

Let's trace through the invalid tree [5, 1, 4, null, null, 3, 6] (Example 2):

The tree looks like:

      5
     / \
    1   4
       / \
      3   6

Step 1: Start at root 5 with range (-∞, +∞).

  • Is 5 within (-∞, +∞)? Yes ✓.
  • Go left to node 1 with range (-∞, 5).
  • Go right to node 4 with range (5, +∞).

Step 2: Visit node 1 with range (-∞, 5).

  • Is 1 within (-∞, 5)? Yes ✓.
  • Node 1 is a leaf, both children are null → return true.

Step 3: Visit node 4 with range (5, +∞).

  • Is 4 within (5, +∞)? We need 4 > 5, but 4 < 5. NO ✗!
  • The range check fails immediately.

Step 4: Return false. Node 4 violates the constraint that all nodes in the right subtree of 5 must have values greater than 5.

Result: Return false.

Min/Max Range Validation — Catching the Violation — Watch how valid ranges shrink as we descend the tree, and how node 4 gets caught violating the range imposed by its ancestor 5.

Algorithm

  1. Define a helper function validate(node, low, high) that checks if a subtree is a valid BST within the range (low, high)
  2. Base case: if node is null, return true (an empty tree is a valid BST)
  3. If node.val ≤ low or node.val ≥ high, return false (value out of valid range)
  4. Recursively check:
    • Left subtree with updated range: validate(node.left, low, node.val)
    • Right subtree with updated range: validate(node.right, node.val, high)
  5. Return true only if both subtrees are valid
  6. Initial call: validate(root, -infinity, +infinity)

Code

class Solution {
public:
    bool validate(TreeNode* node, long low, long high) {
        if (!node) return true;
        
        if (node->val <= low || node->val >= high) {
            return false;
        }
        
        return validate(node->left, low, node->val) &&
               validate(node->right, node->val, high);
    }
    
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }
};
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, low, high):
            if not node:
                return True
            
            if node.val <= low or node.val >= high:
                return False
            
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))
        
        return validate(root, float('-inf'), float('inf'))
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long low, long high) {
        if (node == null) return true;
        
        if (node.val <= low || node.val >= high) {
            return false;
        }
        
        return validate(node.left, low, node.val) &&
               validate(node.right, node.val, high);
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, we visit every node exactly once. Each visit involves a constant-time range check and two recursive calls. If a violation is found, we short-circuit and return early, but worst case (a valid BST) requires checking all n nodes.

Space Complexity: O(h)

The only extra space is the recursion call stack, which is proportional to the height h of the tree. For a balanced BST, h = O(log n). For a completely skewed tree (like a linked list), h = O(n). No additional data structures are used — the range bounds are passed as function parameters on the stack.