51. Validate Binary Search Tree · DSA Practice

Check whether a binary tree is a valid binary search tree: every node’s left subtree holds only smaller values, its right subtree only larger values, and both subtrees are BSTs too.

Example 1

Input: root = [2,1,3]

Output: true

Example 2

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

Output: false

Explanation: 3 sits in the right subtree of 5, so it must be greater than 5.

Hint 1

Checking only parent vs child is not enough.

Hint 2

Pass down the allowed (low, high) range for each subtree.

TreeBSTDFS

Approach 1: In-order must be increasing

In-order traversal of a BST is strictly increasing.

⏱ Time O(n)💾 Space O(h)

Approach 2: Range DFS ✅

Each node narrows the valid range for its children.

⏱ Time O(n)💾 Space O(h)

Reference solution for Range DFS (time O(n), space O(h)). Each solution passes every test in all four languages.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def ok(node, lo, hi):              # every value must lie strictly between lo and hi
            if not node:
                return True
            if not (lo < node.val < hi):
                return False
            return ok(node.left, lo, node.val) and ok(node.right, node.val, hi)
        return ok(root, float('-inf'), float('inf'))

class Solution {
    public boolean isValidBST(TreeNode root) {
        return ok(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean ok(TreeNode node, long lo, long hi) {
        if (node == null) return true;
        if (node.val <= lo || node.val >= hi) return false;
        return ok(node.left, lo, node.val) && ok(node.right, node.val, hi);
    }
}

class Solution {
    bool ok(TreeNode* node, long long lo, long long hi) {
        if (!node) return true;
        if (node->val <= lo || node->val >= hi) return false;
        return ok(node->left, lo, node->val) && ok(node->right, node->val, hi);
    }
public:
    bool isValidBST(TreeNode* root) {
        return ok(root, LLONG_MIN, LLONG_MAX);
    }
};

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Binary Trees & BSTs.