Validate Binary Search Tree

medium
TreesTreeBinary TreeDepth-First Search

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys strictly less than the node's key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Examples

Example 1

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

Example 2

  • Input: root = [5,1,4,null,null,3,6]
  • Output: false
  • Explanation: The root node's value is 5 but its right child's value is 4, which is less than 5.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive Range Validation

Intuition

A common mistake when validating a BST is to only check that each node's value is greater than its left child and less than its right child. This misses cases where a deeper node violates the BST property with respect to an ancestor. The correct approach is to pass down valid range bounds. Each node must fall within a range defined by its ancestors. The root can be any value, its left child must be less than the root, the left child's right child must be less than the root but greater than the left child, and so on. We track these bounds as we recurse.

Algorithm

  1. Define a helper function that takes a node and the valid range (min, max).
  2. If the node is null, return true (empty trees are valid BSTs).
  3. If the node's value is not strictly within (min, max), return false.
  4. Recursively validate the left subtree with the updated range (min, node.val).
  5. Recursively validate the right subtree with the updated range (node.val, max).
  6. Return true only if both subtrees are valid.
TimeO(n)SpaceO(h) where h is the height of the tree

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }

private:
    bool validate(TreeNode* node, long minVal, long maxVal) {
        if (node == nullptr) return true;
        if (node->val <= minVal || node->val >= maxVal) return false;
        return validate(node->left, minVal, node->val) &&
               validate(node->right, node->val, maxVal);
    }
};
Java 21
class Solution {
    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);
    }
}
Python 3.12
def isValidBST(root: Optional[TreeNode]) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return validate(node.left, min_val, node.val) and \
               validate(node.right, node.val, max_val)

    return validate(root, float('-inf'), float('inf'))
Go 1.26
import "math"

func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, minVal, maxVal int64) bool {
    if node == nil {
        return true
    }
    val := int64(node.Val)
    if val <= minVal || val >= maxVal {
        return false
    }
    return validate(node.Left, minVal, val) && validate(node.Right, val, maxVal)
}
Approach 2

Inorder Traversal

Intuition

A key property of a valid BST is that an inorder traversal produces values in strictly ascending order. We can validate the BST by performing an inorder traversal and checking that each value is strictly greater than the previous one. We track the previously visited value and compare it with the current node. If at any point the current value is not greater than the previous value, the tree is not a valid BST. This approach is intuitive because it directly leverages the definition of BST ordering.

Algorithm

  1. Initialize a variable to track the previously visited node's value (start with negative infinity).
  2. Perform an inorder traversal: recurse on left, visit node, recurse on right.
  3. At each node, check if the current value is strictly greater than the previous value.
  4. If not, return false.
  5. Update the previous value to the current node's value.
  6. If the entire traversal completes without violation, return true.
TimeO(n)SpaceO(h) where h is the height of the tree

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return inorder(root, prev);
    }

private:
    bool inorder(TreeNode* node, TreeNode*& prev) {
        if (node == nullptr) return true;
        if (!inorder(node->left, prev)) return false;
        if (prev != nullptr && node->val <= prev->val) return false;
        prev = node;
        return inorder(node->right, prev);
    }
};
Java 21
class Solution {
    private TreeNode prev = null;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return true;
        if (!inorder(node.left)) return false;
        if (prev != null && node.val <= prev.val) return false;
        prev = node;
        return inorder(node.right);
    }
}
Python 3.12
def isValidBST(root: Optional[TreeNode]) -> bool:
    prev = [None]

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if prev[0] is not None and node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)
Go 1.26
import "math"

func isValidBST(root *TreeNode) bool {
    prev := int64(math.MinInt64)
    var inorder func(*TreeNode) bool
    inorder = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if !inorder(node.Left) {
            return false
        }
        if int64(node.Val) <= prev {
            return false
        }
        prev = int64(node.Val)
        return inorder(node.Right)
    }
    return inorder(root)
}

Frequently asked questions

What is the optimal time complexity of Validate Binary Search Tree?

The most efficient approach in this guide ("Inorder Traversal") runs in O(n) time and uses O(h) where h is the height of the tree extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Validate Binary Search Tree use?

Validate Binary Search Tree is a medium-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Validate Binary Search Tree be solved without extra space?

The most space-efficient approach in this guide uses O(h) where h is the height of the tree extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) where h is the height of the tree, while the optimized version uses O(h) where h is the height of the tree.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
root=
[2,1,3]
Expected Output
true