98. Validate Binary Search Tree (Medium)

Problem

Given the root of a binary tree, determine if it is a valid Binary Search Tree:

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

Example

• root = [2,1,3] → true
• root = [5,1,4,null,null,3,6] → false (4 > 3, violating BST)

LeetCode 98 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check “all left < root < all right” at each node

For each node, walk its left subtree confirming all < node, and right subtree confirming all > node.

Python

def is_valid_bst(root):
    def all_less(node, val):           # L1: walk subtree checking < val
        if not node:
            return True
        return node.val < val and all_less(node.left, val) and all_less(node.right, val)

    def all_greater(node, val):        # L2: walk subtree checking > val
        if not node:
            return True
        return node.val > val and all_greater(node.left, val) and all_greater(node.right, val)

    if not root:
        return True
    return (all_less(root.left, root.val)    # L3: O(n) subtree walk
            and all_greater(root.right, root.val)  # L4: O(n) subtree walk
            and is_valid_bst(root.left)            # L5: recurse left
            and is_valid_bst(root.right))          # L6: recurse right

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function isValidBST(root: TreeNode | null): boolean {
    function allLess(node: TreeNode | null, val: number): boolean {  // L1: walk subtree checking < val
        if (!node) return true;
        return node.val < val && allLess(node.left, val) && allLess(node.right, val);
    }
    function allGreater(node: TreeNode | null, val: number): boolean {  // L2: walk subtree checking > val
        if (!node) return true;
        return node.val > val && allGreater(node.left, val) && allGreater(node.right, val);
    }
    if (!root) return true;
    return (allLess(root.left, root.val)          // L3: O(n) subtree walk
         && allGreater(root.right, root.val)       // L4: O(n) subtree walk
         && isValidBST(root.left)                  // L5: recurse left
         && isValidBST(root.right));               // L6: recurse right
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func allLess(node *TreeNode, val int) bool {      // L1: walk subtree checking < val
    if node == nil {
        return true
    }
    return node.Val < val && allLess(node.Left, val) && allLess(node.Right, val)
}

func allGreater(node *TreeNode, val int) bool {   // L2: walk subtree checking > val
    if node == nil {
        return true
    }
    return node.Val > val && allGreater(node.Left, val) && allGreater(node.Right, val)
}

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return allLess(root.Left, root.Val) &&        // L3: O(n) subtree walk
        allGreater(root.Right, root.Val) &&        // L4: O(n) subtree walk
        isValidBST(root.Left) &&                   // L5: recurse left
        isValidBST(root.Right)                     // L6: recurse right
}

Swift

final class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        guard let root else { return true }
        if let maximum = maximum(root.left), maximum >= root.val { return false }
        if let minimum = minimum(root.right), minimum <= root.val { return false }
        return isValidBST(root.left) && isValidBST(root.right)
    }
    private func maximum(_ node: TreeNode?) -> Int? { guard let node else { return nil }; return max(node.val, max(maximum(node.left) ?? node.val, maximum(node.right) ?? node.val)) }
    private func minimum(_ node: TreeNode?) -> Int? { guard let node else { return nil }; return min(node.val, min(minimum(node.left) ?? node.val, minimum(node.right) ?? node.val)) }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1/L2 (subtree walks)	$O(n)$	$O(n)$ calls	$O(n²)$
L3/L4 (all_less/all_greater)	$O(n)$	n nodes	$O(n²)$ ← dominates
L5/L6 (recurse children)	$O(1)$ dispatch	n	$O(n)$

For each node, the subtree walks re-examine every descendant. In a skewed tree of depth n, the same nodes are re-visited $O(n)$ times each, giving $O(n²)$ total.

Complexity

• Time: $O(n²)$ worst case, driven by L3/L4 re-walking subtrees at every node.
• Space: $O(h)$.

Correct but re-walks subtrees many times.

Approach 2: Inorder traversal must be strictly increasing

An inorder walk of a BST yields values in sorted order. Compare each visited value to the previous.

Python

def is_valid_bst(root):
    prev = [float('-inf')]          # L1: mutable cell for prev value

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):  # L2: recurse left, O(h) stack depth
            return False
        if node.val <= prev[0]:     # L3: O(1) monotonicity check
            return False
        prev[0] = node.val          # L4: O(1) update
        return inorder(node.right)  # L5: recurse right

    return inorder(root)

TypeScript

function isValidBST(root: TreeNode | null): boolean {
    let prev = -Infinity;

    function inorder(node: TreeNode | null): boolean {
        if (!node) return true;
        if (!inorder(node.left)) return false;   // L2: recurse left, O(h) stack depth
        if (node.val <= prev) return false;       // L3: O(1) monotonicity check
        prev = node.val;                          // L4: O(1) update
        return inorder(node.right);              // L5: recurse right
    }

    return inorder(root);
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
    prev := -1 << 62
    hasPrev := false
    var inorder func(*TreeNode) bool
    inorder = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if !inorder(node.Left) {                 // L2: recurse left, O(h) stack depth
            return false
        }
        if hasPrev && node.Val <= prev {
            return false                          // L3: O(1) monotonicity check
        }
        prev = node.Val                           // L4: O(1) update
        hasPrev = true
        return inorder(node.Right)               // L5: recurse right
    }
    return inorder(root)
}

Swift

final class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        var previous: Int?
        var valid = true
        func traverse(_ node: TreeNode?) {
            guard let node, valid else { return }
            traverse(node.left)
            if let previous, node.val <= previous { valid = false; return }
            previous = node.val
            traverse(node.right)
        }
        traverse(root)
        return valid
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2 (recurse left)	$O(1)$ dispatch	n	$O(n)$
L3 (compare prev)	$O(1)$	n	$O(n)$
L4 (update prev)	$O(1)$	n	$O(n)$
L5 (recurse right)	$O(1)$ dispatch	n	$O(n)$ ← dominates (all lines tie)

Every node is visited exactly once. All lines contribute $O(n)$ total; the whole traversal is $O(n)$.

Complexity

• Time: $O(n)$, each node visited once via L2/L5.
• Space: $O(h)$ recursion.

Elegant; the BST’s defining property makes this a one-liner-ish implementation.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Recursive with (low, high) bounds (optimal)

Pass tightening bounds down the tree: at any node, every value must fit strictly within (low, high). When recursing left, high becomes the node’s value; when recursing right, low becomes the node’s value.

Python

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):  # L1: O(1) bounds check
            return False
        return (validate(node.left, low, node.val)    # L2: tighten high
                and validate(node.right, node.val, high))  # L3: tighten low
    return validate(root, float('-inf'), float('inf'))

TypeScript

function isValidBST(root: TreeNode | null): boolean {
    function validate(node: TreeNode | null, low: number, high: number): boolean {
        if (!node) return true;
        if (!(low < node.val && node.val < high)) return false;  // L1: O(1) bounds check
        return (validate(node.left, low, node.val)               // L2: tighten high
             && validate(node.right, node.val, high));           // L3: tighten low
    }
    return validate(root, -Infinity, Infinity);
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
    var validate func(*TreeNode, int, int) bool
    validate = func(node *TreeNode, low, high int) bool {
        if node == nil {
            return true
        }
        if !(low < node.Val && node.Val < high) {
            return false                                        // L1: O(1) bounds check
        }
        return validate(node.Left, low, node.Val) &&           // L2: tighten high
            validate(node.Right, node.Val, high)               // L3: tighten low
    }
    return validate(root, -1<<62, 1<<62)
}

Swift

final class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        func validate(_ node: TreeNode?, _ low: Int?, _ high: Int?) -> Bool {
            guard let node else { return true }
            if let low, node.val <= low { return false }
            if let high, node.val >= high { return false }
            return validate(node.left, low, node.val) && validate(node.right, node.val, high)
        }
        return validate(root, nil, nil)
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (bounds check)	$O(1)$	n	$O(n)$
L2/L3 (recurse children)	$O(1)$ dispatch	n	$O(n)$ ← dominates (all lines tie)

Each node is visited exactly once, with $O(1)$ work per node. The bounds are passed as scalars so there is no copying cost.

Complexity

• Time: $O(n)$, driven by L2/L3 visiting every node once.
• Space: $O(h)$ recursion.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Nested all-less / all-greater	$O(n²)$	$O(h)$
Inorder monotonic check	$O(n)$	$O(h)$
Recursive bounds	$O(n)$	$O(h)$

Both Approach 2 and Approach 3 are $O(n)$; the bounds version scales more naturally to variants that need upper/lower constraints (insertion, range counting).

Test cases

Python

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            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'))

def _run_tests():
    # [2,1,3] → True
    assert is_valid_bst(build_tree([2, 1, 3])) == True
    # [5,1,4,null,null,3,6] → False (4 is root of right subtree but 4 < 5)
    assert is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6])) == False
    # single node → True
    assert is_valid_bst(build_tree([1])) == True
    # empty → True
    assert is_valid_bst(None) == True
    # [3,1,5,0,2,4,6] → True (full balanced BST)
    assert is_valid_bst(build_tree([3, 1, 5, 0, 2, 4, 6])) == True
    # [5,4,6,null,null,3,7] → False (3 in right subtree is < root 5)
    assert is_valid_bst(build_tree([5, 4, 6, None, None, 3, 7])) == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function isValidBST(root: TreeNode | null): boolean {
    function validate(node: TreeNode | null, low: number, high: number): boolean {
        if (!node) return true;
        if (!(low < node.val && node.val < high)) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
    return validate(root, -Infinity, Infinity);
}

console.assert(isValidBST(buildTree([2, 1, 3])) === true);
console.assert(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])) === false);
console.assert(isValidBST(buildTree([1])) === true);
console.assert(isValidBST(null) === true);
console.assert(isValidBST(buildTree([3, 1, 5, 0, 2, 4, 6])) === true);
console.assert(isValidBST(buildTree([5, 4, 6, null, null, 3, 7])) === false);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, BST invariant propagation

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.