Validate Binary Search Tree

Difficulty: Medium Source: NeetCode

Problem

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 valid BSTs.

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.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• BST Property — Every node must satisfy constraints relative to ALL ancestors, not just its parent
• DFS with Bounds — Passing min/max constraints down the tree
• Inorder Traversal — Inorder of a valid BST produces a strictly increasing sequence

1. Brute Force: Inorder Traversal

Intuition

Inorder traversal of a valid BST always produces values in strictly increasing order. So we can do an inorder traversal, collect values, and check that each value is strictly greater than the previous one.

Algorithm

1. Perform inorder traversal to get values in order
2. Check that the list is strictly increasing

Solution

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

def is_valid_bst_inorder(root):
    values = []

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

    inorder(root)

    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:  # Must be strictly increasing
            return False
    return True

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        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

# --- tests ---
root1 = build_tree([2, 1, 3])
print(is_valid_bst_inorder(root1))  # True

root2 = build_tree([5, 1, 4, None, None, 3, 6])
print(is_valid_bst_inorder(root2))  # False

root3 = build_tree([5, 4, 6, None, None, 3, 7])
print(is_valid_bst_inorder(root3))  # False (3 < 5 but it's in right subtree)

Complexity

• Time: O(n) — full traversal
• Space: O(n) — storing all node values

2. Optimal: DFS with Min/Max Bounds

Intuition

At each node, instead of checking only against its parent, we track the valid range (min, max) that the node’s value must fall within. When going left, the upper bound tightens to the current node’s value. When going right, the lower bound tightens. This catches the case where a value in the right subtree of an ancestor is less than that ancestor’s value.

Algorithm

1. Define dfs(node, min_val, max_val) returning bool
2. Base case: null node is valid
3. If node.val <= min_val or node.val >= max_val, return false
4. Recurse: left with (min_val, node.val), right with (node.val, max_val)
5. Start with dfs(root, -inf, +inf)

Solution

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

def is_valid_bst(root):
    def dfs(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        # Left subtree: all values must be < node.val (tighten upper bound)
        # Right subtree: all values must be > node.val (tighten lower bound)
        return (dfs(node.left, min_val, node.val) and
                dfs(node.right, node.val, max_val))

    return dfs(root, float('-inf'), float('inf'))

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        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

# --- tests ---
root1 = build_tree([2, 1, 3])
print(is_valid_bst(root1))  # True

root2 = build_tree([5, 1, 4, None, None, 3, 6])
print(is_valid_bst(root2))  # False

# Tricky: [5,4,6,null,null,3,7] — node 3 is in right subtree of 5, violates BST
root3 = build_tree([5, 4, 6, None, None, 3, 7])
print(is_valid_bst(root3))  # False

root4 = build_tree([1, 1])  # Duplicate values — not a valid BST
print(is_valid_bst(root4))  # False

Complexity

• Time: O(n) — each node visited once
• Space: O(h) — recursion stack

Common Pitfalls

Only comparing against the parent node. A node [5, 4, 6, null, null, 3, 7] fails because 3 is in the right subtree of 5 but less than 5. Checking only 3 > 6 (parent) passes, but we also need 3 > 5 (grandparent). The min/max bounds approach handles this automatically.

Not handling duplicates. BSTs require strictly less than and strictly greater than. If node.val == parent.val, that’s invalid. Make sure to use <= and >= in the bounds check.

Using integer limits instead of infinity. The problem says values can be up to 2^31 - 1, so if you initialize bounds to INT_MAX/INT_MIN, you’ll get false results for those edge values. Use float('inf') to be safe.