Validate Binary Search Tree — DSA · Engineering Playbook

Problem#

Given the root of a binary tree, return whether it’s a valid BST: left subtree’s values strictly less than node, right subtree strictly greater, both subtrees themselves valid.

Examples#

[2,1,3] → true
[5,1,4,null,null,3,6] → false

Constraints#

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

Approach#

DFS carrying a (lo, hi) exclusive range. Each node must satisfy lo < val < hi. Recurse into left with hi = val, into right with lo = val. Use long long bounds (or pointers) to handle int extremes.

Solution#

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        function<bool(TreeNode*, long, long)> dfs = [&](TreeNode* u, long lo, long hi) {
            if (!u) return true;
            if (u->val <= lo || u->val >= hi) return false;
            return dfs(u->left, lo, u->val) && dfs(u->right, u->val, hi);
        };
        return dfs(root, LONG_MIN, LONG_MAX);
    }
};

import "math"

func isValidBST(root *TreeNode) bool {
    var dfs func(u *TreeNode, lo, hi int) bool
    dfs = func(u *TreeNode, lo, hi int) bool {
        if u == nil {
            return true
        }
        if u.Val <= lo || u.Val >= hi {
            return false
        }
        return dfs(u.Left, lo, u.Val) && dfs(u.Right, u.Val, hi)
    }
    return dfs(root, math.MinInt64, math.MaxInt64)
}

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(u: Optional[TreeNode], lo: float, hi: float) -> bool:
            if u is None:
                return True
            if u.val <= lo or u.val >= hi:
                return False
            return dfs(u.left, lo, u.val) and dfs(u.right, u.val, hi)

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

function isValidBST(root) {
    const dfs = (u, lo, hi) => {
        if (!u) return true;
        if (u.val <= lo || u.val >= hi) return false;
        return dfs(u.left, lo, u.val) && dfs(u.right, u.val, hi);
    };
    return dfs(root, -Infinity, Infinity);
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode u, long lo, long hi) {
        if (u == null) return true;
        if (u.val <= lo || u.val >= hi) return false;
        return dfs(u.left, lo, u.val) && dfs(u.right, u.val, hi);
    }
}

function isValidBST(root: TreeNode | null): boolean {
    const dfs = (u: TreeNode | null, lo: number, hi: number): boolean => {
        if (!u) return true;
        if (u.val <= lo || u.val >= hi) return false;
        return dfs(u.left, lo, u.val) && dfs(u.right, u.val, hi);
    };
    return dfs(root, -Infinity, Infinity);
}

Editorial#

A common bug is only checking direct children — but BST validity is global: a node’s right subtree must all stay below its parent’s bound. Threading the interval through DFS captures this perfectly.

Complexity#

Time: O(n).
Space: O(h).

Concept revision#

Kth Smallest Element in a BST

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#