Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Medium

Validate Binary Search Tree

Validate a binary search tree explained: why checking only parent and child fails, the min/max bounds fix, tested Python code, edge cases and a live BST visual.

Also searched as: check if a binary tree is a BST · is valid BST with min and max bounds

🌳

Try it live Free

Binary Search Tree & Traversals

Insert values in the BST lab and run in-order: a valid BST always prints its values in increasing order, which is the second way to validate one.

Open the playground →

The problem

Given the root of a binary tree, decide whether it is a valid binary search tree: for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger, and both subtrees are BSTs themselves.

Inputroot = [2, 1, 3]
OutputTrue
Inputroot = [5, 1, 4, null, null, 3, 6]
OutputFalse

3 sits in the right subtree of 5 but is smaller than 5.

The key insight

Comparing each node only with its direct children is the classic trap: a value deep in the right subtree can still be smaller than an ancestor. The fix is to pass down an allowed range (low, high). Going left tightens the upper bound to the current value; going right tightens the lower bound. Every node must fall strictly inside its range.

Brute force first: Collecting the inorder traversal and checking it is strictly increasing is also O(n) and correct; it just uses O(n) extra space for the list.

Step-by-step approach

  1. Start at the root with the range (-inf, +inf).
  2. If the node is None, it is valid.
  3. If node.val is not strictly between low and high, return False.
  4. Recurse left with range (low, node.val) and right with range (node.val, high).
  5. The tree is valid only if both recursive calls are valid.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def is_valid_bst(root):
    def ok(node, low, high):
        if node is None:
            return True
        if not (low < node.val < high):
            return False
        return ok(node.left, low, node.val) and ok(node.right, node.val, high)
    return ok(root, float("-inf"), float("inf"))

Complexity

TimeO(n)
SpaceO(h)

Each node is checked once against its range. The recursion depth is the tree height h.

Common mistakes

Frequently asked questions

What is the time and space complexity of validating a BST?

O(n) time because each node is checked once, and O(h) space for the recursion stack. The inorder-list approach adds O(n) for the list.

Why is checking parent and child not enough?

The BST rule applies to whole subtrees, not just children. A node can be larger than its parent yet smaller than its grandparent while sitting in the grandparent's right subtree, which breaks the rule.

How do I validate using inorder traversal?

Do an inorder walk while remembering the previous value. If any value is not strictly greater than the previous one, the tree is not a BST. This uses O(h) space if you keep only the previous value.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.