MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Validate Binary Search Tree

1 approach, code in every language

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

A BST is valid when, for every node, all values in its entire left subtree are strictly less than the node's value and all values in its entire right subtree are strictly greater. The rule applies to whole subtrees, not just direct children, so a value that is fine relative to its parent can still violate an ancestor's bound.

Example 1

Input: root = [2,1,3]

Output: true

1 < 2 < 3, and each subtree respects the ordering, so the tree is a valid BST.

Example 2

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

Output: false

The root is 5, but its right subtree contains 3, which is less than 5. That breaks the BST rule, so the answer is false.

Constraints

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

Range-Bounds DFS

Recurse while threading down an open (low, high) interval; every node must fall strictly inside its interval.

Loading animation…

Intuition

Checking a node only against its immediate children is not enough, because a deep descendant can still violate an ancestor's constraint. Instead, carry an allowed open interval (low, high) into every call that captures the strictest bounds imposed by all ancestors. A node is valid only if its value lies strictly between low and high. When we descend left, the current value becomes the new upper bound; when we descend right, it becomes the new lower bound. An equivalent approach is to perform an inorder traversal and confirm the values come out in strictly increasing order, since inorder on a valid BST is always sorted.

Algorithm walkthrough

1Call a helper on the root with an unbounded interval: low = -infinity and high = +infinity.
2If the current node is null, it satisfies the rule vacuously, so return true.
3If the node's value is not strictly greater than low or not strictly less than high, return false.
4Recurse left with the interval (low, node.val), tightening the upper bound to the current value.
5Recurse right with the interval (node.val, high), tightening the lower bound to the current value.
6Return true only when both recursive checks succeed for every node.

Implementation

class Solution:
    def isValidBST(self, root: 'TreeNode') -> bool:
        def validate(node, low, high):
            if node is None:
                return True
            if not (low < 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'))

Time

O(n)

Space

O(h)

Each node is examined once for O(n) time. The recursion stack is O(h), ranging from O(log n) for a balanced tree to O(n) for a skewed one.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Archive Index Order is our own problem on the technique behind Validate Binary Search Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free