Skip to main content
DSA patterns

Validate Binary Search Tree

mediumTrees Must-doAmazonMicrosoftCisco

Problem statement

You are given the root of a binary tree. Return true if it is a valid binary search tree (BST), and false if it is not.

A tree is a valid BST when, for every node:

  • every value in its left subtree is strictly smaller than the node's value,
  • every value in its right subtree is strictly larger than the node's value,
  • and both subtrees are valid BSTs too.

"Strictly" means equal values are not allowed. Node values can be as small as -2³¹ and as large as 2³¹ - 1, so be careful when you pick "smaller than anything" or "larger than anything" limits.

The tree is written in level order, with null where a child is missing. Think of it as a sanity check on an ordered index — such as a sorted routing table stored as a tree — before you trust lookups on it.

Examples

Example 1

Input: root = [2,1,3]

Output: true

Explanation: 1 is on the left of 2 and is smaller; 3 is on the right and is larger. Both children are leaves, so the tree is valid.

Example 1

Example 2

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

Output: false

Explanation: 4 is in the right subtree of 5, so it must be larger than 5, but it is smaller. One broken rule is enough to make the tree invalid.

Example 2

Hints

Hint 1: Checking only that each node's left child is smaller and right child is larger is not enough. Try the tree [5,4,6,null,null,3,7]: every parent–child pair looks fine, but 3 sits in 5's right subtree.

Approach

Optimal: Range check

Intuition

Instead of looking up at the subtrees, pass limits down from the top. The root can hold any value. When you step to a node's left child, that child — and everything below it — must be smaller than the node, so the node's value becomes the new upper limit. When you step right, the node's value becomes the new lower limit.

Each node then only has to check one thing: "is my value strictly between low and high?" The limits carry the information from all ancestors, which is exactly what the simple parent–child check misses. For the starting limits, use values outside the int range (a 64-bit long, or "no limit" in Python), because a node can legally hold -2³¹ or 2³¹ - 1.

Steps

  1. Call check(root, low = −∞, high = +∞).
  2. In check(node, low, high):
    • If node is empty, return true.
    • If node.val <= low or node.val >= high, return false.
    • Return check(node.left, low, node.val) and check(node.right, node.val, high).

Dry run

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

node allowed range inside?
5 (−∞, +∞) yes
1 (−∞, 5) yes; no children
4 (5, +∞) no → return false

Nodes 3 and 6 are never visited. Edge cases: a single node with value -2³¹ passes, because the starting limits lie outside the int range. The hint's tree [5,4,6,null,null,3,7] fails at 3, whose range is (5, 6).

Complexity

Time O(n) - Each node is visited exactly once, and each visit does two comparisons. There is no list and no second pass. The walk can also stop early at the first node that breaks the rule. In the worst case (a valid tree) it still visits all n nodes.

Space O(H) - Only the recursion stack is used, one frame per level of the path we are on. H is O(log n) for a balanced tree and O(n) for a line-shaped one. No list of values is stored. The input tree is not counted.

from collections import deque
from typing import Optional


# Definition for a binary tree node (LeetCode's).
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: Optional[TreeNode]) -> bool:
        def check(node: Optional[TreeNode], low: float, high: float) -> bool:
            if node is None:
                return True
            if node.val <= low or node.val >= high:
                return False
            return check(node.left, low, node.val) and check(node.right, node.val, high)

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


def build_tree(values: list) -> Optional[TreeNode]:
    """Build a tree from level-order values, None = missing child."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


if __name__ == "__main__":
    print(str(Solution().isValidBST(build_tree([2, 1, 3]))).lower())  # true
    print(str(Solution().isValidBST(build_tree([5, 1, 4, None, None, 3, 6]))).lower())  # false
RecapThe whole problem in a few lines, for the night before
  • Spot it: "is this binary tree a valid BST?" — a rule that holds for whole subtrees, not just children
  • Idea: pass a range (low, high) down the tree; going left the node becomes high, going right it becomes low
  • Cost: O(n) time, O(H) space for the recursion
  • Trap: only comparing a node with its children misses [5,4,6,null,null,3,7]; and int limits break on values equal to INT_MIN / INT_MAX — use long or "no limit"
  • Remember: in-order of a valid BST is strictly increasing — checking that is an equal alternative

Interview follow-ups

  • Do it without recursion.

    Use an explicit stack for an iterative in-order walk: go as far left as you can pushing nodes, pop one, compare it with the previous value, then move to its right child. Stop with false the moment a value is not larger than the previous one. Time stays O(n) and the stack holds O(H) nodes, but a very deep tree can no longer overflow the call stack.

  • The tree is valid except that two nodes were swapped by mistake. How do you find them?

    Do an in-order walk and look for places where a value is smaller than the one before it. If the swapped nodes were next to each other there is one such drop; otherwise there are two. The first wrong node is the larger value at the first drop, and the second is the smaller value at the last drop. This is the classic "Recover Binary Search Tree" problem and costs O(n) time.

  • The tree can have duplicates, and duplicates must go to the left. What changes?

    Only the comparisons. With the range check, the left side allows node.val == high, so the test becomes node.val <= low or node.val > high. Everything else — the walk, the time and the space — stays the same. State the rule before you code, because interviewers often leave it vague on purpose.

Frequently asked questions

Because the BST rule is about whole subtrees, not just direct children. In [5,4,6,null,null,3,7], node 6 has children 3 and 7, and 3 < 6 < 7 looks fine. But 3 is in the right subtree of 5, so it must be larger than 5. Only a check that carries limits from all ancestors (or an in-order check) catches this.

Node values can be exactly Integer.MIN_VALUE or Integer.MAX_VALUE. If you start with int limits, a single node holding Integer.MIN_VALUE would fail the node.val <= low check even though it's valid. A 64-bit long starts strictly outside the int range, so every real value fits. Another option is to pass null for "no limit".

Yes. Keep only the previous value you visited (starting as "none"). During the in-order walk, if the current value is <= the previous one, return false; otherwise update the previous value. That has the same O(n) time and O(H) space as the range check, so it is also an optimal solution — pick whichever you find easier to explain.

Not in this problem: both sides must be strictly smaller or larger. Some real BSTs allow duplicates on one side (for example, equal keys always go right). In that case, change the matching comparison from >= to > (or <= to <) on that side only, and say which rule you picked out loud in the interview.

Sorted structures back a lot of infra: ordered indexes, interval maps for IP ranges, and sorted routing tables. A check like this is how you catch a corrupted or badly built index before it gives wrong lookups. It is also a quick test of whether you understand that a rule on "the whole subtree" needs information passed down from ancestors.