Validate Binary Search Tree

Medium Problem 73 of 151 Java and Python

Problem

Given the root of a binary tree, determine whether it is a valid binary search tree (BST):

Every node in a node's left subtree has a smaller value, every node in its right subtree has a larger value, and both subtrees are BSTs too.

Example 1

Input: root = [2, 1, 3]
Output: true

Example 2

Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
Why: 4 is in the right subtree of 5 but is smaller than 5.

Example 3

Input: root = [5, 4, 6, null, null, 3, 7]
Output: false
Why: 3 is less than its parent 6 correctly, but it is in the right subtree of 5.

Constraints

1 ≤ number of nodes ≤ 10⁴
-2³¹ ≤ Node.val ≤ 2³¹ – 1

Explanation

Comparing each node only with its children is the classic trap: the third example passes that check but is not a BST. A node must respect every ancestor.

Pass down a range (low, high). Going left, the current value becomes the new upper bound; going right, it becomes the new lower bound.

Approach 1 · Naive

Inorder must be strictly increasing

Time O(n)
Space O(n)

An inorder traversal of a BST is sorted. Collect it and check every value is larger than the one before.

Collect values by inorder traversal.
Return whether each value is strictly greater than the previous one.

Java

import java.util.*;

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

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

Python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        values = []

        def inorder(node):
            if node:
                inorder(node.left)
                values.append(node.val)
                inorder(node.right)

        inorder(root)
        return all(values[i] > values[i - 1] for i in range(1, len(values)))

Approach 2 · Optimal

Recursion with bounds

Time O(n)
Space O(h)

Each node must lie strictly between the bounds its ancestors impose.

valid(node, low, high): null is valid.
If node.val <= low or node.val >= high, return false.
Return valid(left, low, node.val) && valid(right, node.val, high), starting with (-∞, +∞).

Java

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

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

Python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, low, high):
            if not node:
                return True
            if not low < node.val < high:
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, float("-inf"), float("inf"))

Complexity compared

Approach	Time	Space
Naive Inorder must be strictly increasing	O(n)	O(n)
Optimal Recursion with bounds	O(n)	O(h)

Key takeaways

Use long bounds in Java: node values can be Integer.MIN_VALUE or Integer.MAX_VALUE.
Duplicates are not allowed here, hence the strict comparisons.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem