Validate Binary Search Tree (LC 98): Range Bounds and Inorder

Check whether a binary tree is a valid BST, where every node must be greater than everything in its left subtree and smaller than everything in its right. Pass down (low, high) bounds or check that the inorder walk strictly increases. O(n) time, O(h) space.

Language Selection

Choose your preferred programming language

Showing: Python

Validate Binary Search Tree

Problem Statement

Given the root of a binary tree, return true if it is a valid binary search tree (BST) and false otherwise.

A tree is a valid BST when, for every node:

  • every value in the node’s left subtree is strictly smaller than the node’s value,
  • every value in the node’s right subtree is strictly larger than the node’s value, and
  • both subtrees are valid BSTs themselves.

“Strictly” means equal values are not allowed anywhere in the tree. Note that the rule covers whole subtrees, not just the direct children.

Examples

Example 1:

Input: root = [5,2,8,1,3]
Output: true
Explanation: 1 < 2 < 3 on the left side, everything left of 5 is smaller than 5,
and 8 on the right is larger than 5.

Example 2:

Input: root = [5,2,8,null,null,4,9]
Output: false
Explanation: Node 8 has children 4 and 9, so 8 on its own looks fine. But 4 sits in the
right subtree of 5 and is smaller than 5, which breaks the rule at the root.

Example 3:

Input: root = [-2147483648,null,2147483647]
Output: true
Explanation: The root holds the smallest 32-bit integer and its right child the largest.
The tree is valid; a solution that uses these two numbers as "no limit" markers gets it wrong.

Constraints

  • The tree has between 1 and 10^4 nodes.
  • -2^31 <= Node.val <= 2^31 - 1

Approach 1: DFS with a Valid Range per Node

Algorithm

Checking each node against its children only is not enough (Example 2 passes that test). Instead, think about what the ancestors require. Every time you go left from a node with value v, everything below must be < v; every time you go right, everything below must be > v. So each node inherits an open interval (low, high) that its value must fall in:

  • The root’s interval is unbounded: (-infinity, +infinity).
  • A node with value v and interval (low, high) passes (low, v) to its left child and (v, high) to its right child.

The tree is valid exactly when every node’s value lies strictly inside its interval.

The bounds need a representation of “no limit” that no node value can equal. Node values use the entire 32-bit range, so Integer.MIN_VALUE and Integer.MAX_VALUE cannot serve as “unbounded”. The code below stores bounds in a wider type (64-bit integers, or infinity in Python and JavaScript), which is always outside the value range. Nullable bounds work equally well.

The natural way to write this is recursion, but a tree with 10^4 nodes can be a single chain 10^4 levels deep, which can overflow the default call stack in several languages. The code keeps the same logic and uses an explicit stack of (node, low, high) entries instead.

  1. Push (root, -infinity, +infinity) onto a stack.
  2. While the stack is not empty, pop (node, low, high):
    • If node.val <= low or node.val >= high, return false.
    • Push the right child with (node.val, high) and the left child with (low, node.val), skipping null children.
  3. Return true.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import math
from typing import Optional


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        # Each entry: a node and the open interval (low, high) its value must lie in.
        # Infinite bounds can never equal a node value, unlike -2**31 or 2**31 - 1.
        stack = [(root, -math.inf, math.inf)]
        while stack:
            node, low, high = stack.pop()
            if not (low < node.val < high):
                return False
            # Going right raises the lower bound; going left lowers the upper bound
            if node.right:
                stack.append((node.right, node.val, high))
            if node.left:
                stack.append((node.left, low, node.val))
        return True

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    // A node and the open interval (low, high) its value must lie in.
    // long bounds sit outside the int range, so they never equal a node value.
    private record Frame(TreeNode node, long low, long high) {}

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // Explicit stack: a 10^4-deep chain could overflow the call stack with recursion
        Deque<Frame> stack = new ArrayDeque<>();
        stack.push(new Frame(root, Long.MIN_VALUE, Long.MAX_VALUE));
        while (!stack.isEmpty()) {
            Frame f = stack.pop();
            long val = f.node().val;
            if (val <= f.low() || val >= f.high()) {
                return false;
            }
            // Going right raises the lower bound; going left lowers the upper bound
            if (f.node().right != null) {
                stack.push(new Frame(f.node().right, val, f.high()));
            }
            if (f.node().left != null) {
                stack.push(new Frame(f.node().left, f.low(), val));
            }
        }
        return true;
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "math"

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // A node and the open interval (low, high) its value must lie in.
    // int64 extremes sit outside the 32-bit value range, so they never equal a node value.
    type frame struct {
        node      *TreeNode
        low, high int64
    }
    stack := []frame{{root, math.MinInt64, math.MaxInt64}}
    for len(stack) > 0 {
        f := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        val := int64(f.node.Val)
        if val <= f.low || val >= f.high {
            return false
        }
        // Going right raises the lower bound; going left lowers the upper bound
        if f.node.Right != nil {
            stack = append(stack, frame{f.node.Right, val, f.high})
        }
        if f.node.Left != nil {
            stack = append(stack, frame{f.node.Left, f.low, val})
        }
    }
    return true
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if (root === null) {
        return true;
    }
    // Each entry: a node and the open interval (low, high) its value must lie in.
    // Infinite bounds can never equal a node value. Explicit stack avoids deep recursion.
    const stack = [[root, -Infinity, Infinity]];
    while (stack.length > 0) {
        const [node, low, high] = stack.pop();
        if (node.val <= low || node.val >= high) {
            return false;
        }
        // Going right raises the lower bound; going left lowers the upper bound
        if (node.right !== null) {
            stack.push([node.right, node.val, high]);
        }
        if (node.left !== null) {
            stack.push([node.left, low, node.val]);
        }
    }
    return true;
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public bool IsValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // A node and the open interval (low, high) its value must lie in.
        // long bounds sit outside the int range, so they never equal a node value.
        // Explicit stack: a 10^4-deep chain could overflow the call stack with recursion.
        var stack = new Stack<(TreeNode node, long low, long high)>();
        stack.Push((root, long.MinValue, long.MaxValue));
        while (stack.Count > 0) {
            var (node, low, high) = stack.Pop();
            if (node.val <= low || node.val >= high) {
                return false;
            }
            // Going right raises the lower bound; going left lowers the upper bound
            if (node.right != null) {
                stack.Push((node.right, node.val, high));
            }
            if (node.left != null) {
                stack.Push((node.left, low, node.val));
            }
        }
        return true;
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <climits>
#include <vector>
using namespace std;

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        // A node and the open interval (low, high) its value must lie in.
        // long long bounds sit outside the int range, so they never equal a node value.
        struct Frame {
            TreeNode* node;
            long long low, high;
        };
        vector<Frame> stack{{root, LLONG_MIN, LLONG_MAX}};
        while (!stack.empty()) {
            Frame f = stack.back();
            stack.pop_back();
            long long val = f.node->val;
            if (val <= f.low || val >= f.high) {
                return false;
            }
            // Going right raises the lower bound; going left lowers the upper bound
            if (f.node->right != nullptr) {
                stack.push_back({f.node->right, val, f.high});
            }
            if (f.node->left != nullptr) {
                stack.push_back({f.node->left, f.low, val});
            }
        }
        return true;
    }
};

Complexity Analysis

  • Time: O(n). Each node is pushed and popped once and checked in O(1).
  • Space: O(h), where h is the height of the tree. The stack holds the nodes along the current path plus at most one pending right child per level: O(log n) for a balanced tree and O(n) for a chain.

Approach 2: Iterative Inorder Traversal (Optimal)

Algorithm

An inorder traversal (left subtree, node, right subtree) of a BST visits the values in sorted order, and with distinct values the order is strictly increasing. The converse also holds: if the inorder sequence is strictly increasing, the tree is a valid BST. So walk the tree in order and compare each value with the one visited just before it.

This needs no sentinel at all. Remember the previously visited node (null at the start) instead of a “previous value” initialised to some minimum, which would wrongly reject a tree whose first value is -2^31.

The walk uses the standard iterative inorder pattern, so deep trees cannot overflow the call stack, and it stops at the first out-of-order pair.

  1. Start with an empty stack, prev = null and node = root.
  2. While node is not null or the stack is not empty:
    • Push node and move to node.left until node is null.
    • Pop the top node. This is the next node in sorted order.
    • If prev is not null and node.val <= prev.val, return false.
    • Set prev = node, then move to node.right.
  3. Return true.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack = []
        prev = None  # last visited node; no sentinel value needed
        node = root
        while node or stack:
            # Walk as far left as possible
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            # Inorder of a valid BST is strictly increasing
            if prev is not None and node.val <= prev.val:
                return False
            prev = node
            node = node.right
        return True

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null; // last visited node; no sentinel value needed
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            // Walk as far left as possible
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            // Inorder of a valid BST is strictly increasing
            if (prev != null && node.val <= prev.val) {
                return false;
            }
            prev = node;
            node = node.right;
        }
        return true;
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    var prev *TreeNode // last visited node; no sentinel value needed
    node := root
    for node != nil || len(stack) > 0 {
        // Walk as far left as possible
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // Inorder of a valid BST is strictly increasing
        if prev != nil && node.Val <= prev.Val {
            return false
        }
        prev = node
        node = node.Right
    }
    return true
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    const stack = [];
    let prev = null; // last visited node; no sentinel value needed
    let node = root;
    while (node !== null || stack.length > 0) {
        // Walk as far left as possible
        while (node !== null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        // Inorder of a valid BST is strictly increasing
        if (prev !== null && node.val <= prev.val) {
            return false;
        }
        prev = node;
        node = node.right;
    }
    return true;
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public bool IsValidBST(TreeNode root) {
        var stack = new Stack<TreeNode>();
        TreeNode prev = null; // last visited node; no sentinel value needed
        TreeNode node = root;
        while (node != null || stack.Count > 0) {
            // Walk as far left as possible
            while (node != null) {
                stack.Push(node);
                node = node.left;
            }
            node = stack.Pop();
            // Inorder of a valid BST is strictly increasing
            if (prev != null && node.val <= prev.val) {
                return false;
            }
            prev = node;
            node = node.right;
        }
        return true;
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <stack>
using namespace std;

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> pending;
        TreeNode* prev = nullptr; // last visited node; no sentinel value needed
        TreeNode* node = root;
        while (node != nullptr || !pending.empty()) {
            // Walk as far left as possible
            while (node != nullptr) {
                pending.push(node);
                node = node->left;
            }
            node = pending.top();
            pending.pop();
            // Inorder of a valid BST is strictly increasing
            if (prev != nullptr && node->val <= prev->val) {
                return false;
            }
            prev = node;
            node = node->right;
        }
        return true;
    }
};

Complexity Analysis

  • Time: O(n) in the worst case, when the tree is valid and every node is visited. An invalid tree is rejected at the first out-of-order pair.
  • Space: O(h) for the stack, which holds at most one path from the root: O(log n) for a balanced tree and O(n) for a chain.

Key Insights

  • The BST rule is about whole subtrees. A node must be compared with all of its ancestors’ constraints, not just its parent. Passing (low, high) down the tree carries exactly those constraints.
  • Each node’s constraints collapse into one interval. However many ancestors there are, only the nearest “turned left at” and “turned right at” values matter, which is why two numbers are enough.
  • Inorder order is the BST property in disguise. Strictly increasing inorder output is equivalent to being a valid BST, so the check becomes “is this sequence sorted?”.
  • Sentinels must lie outside the value range. With values covering all 32-bit integers, use 64-bit bounds, infinities, nullable bounds, or a previous-node pointer.
  • Strict inequality. Duplicates are invalid, so the comparisons are <= / >= for rejection, not < / >.

Edge Cases

  1. A single node: always valid, including when its value is -2^31 or 2^31 - 1.
  2. Extreme values, like [-2147483648,null,2147483647] (valid) or [2147483647,2147483647] (invalid, a duplicate).
  3. A violation deep in the tree that the direct parent does not catch (Example 2): needs ancestor bounds or the inorder check.
  4. Duplicates, like [3,3] or [3,null,3]: both invalid.
  5. A chain of 10^4 nodes, all increasing to the right or decreasing to the left: valid, and deep enough to overflow a recursive solution in some languages.
  6. A valid-looking subtree on the wrong side, like a right subtree that is a perfect BST but contains one value smaller than the root.

Common Mistakes

  1. Only comparing each node with its children. Example 2 passes that test but is not a BST.
  2. Using Integer.MIN_VALUE / Integer.MAX_VALUE as “no bound”. A node holding one of those values is then rejected, as in Example 3. In C++ and C#, the same applies to INT_MIN/int.MinValue.
  3. Initialising “previous value” to the minimum int in the inorder approach, which rejects a tree whose smallest value is -2^31. Track the previous node, or use a flag.
  4. Allowing equal values. Using < instead of <= when rejecting lets [3,3] through.
  5. Deep recursion on a degenerate tree. A 10^4-level chain can overflow the default stack in Python (limit 1000) and, depending on settings, in Java, JavaScript and C#.

Interview Tips

  1. Start with the counterexample to the “check only children” idea; it shows you understand why bounds are needed.
  2. Explain the interval rule in one sentence: going left caps the upper bound, going right raises the lower bound.
  3. Raise the sentinel issue before the interviewer does. Mention that values span the full int range and say how your bounds avoid it.
  4. Offer the inorder version as an alternative and note it needs no sentinels at all when you track the previous node.
  5. Talk about recursion depth. The recursive form is shorter to write; say you would use an explicit stack for a degenerate 10^4-deep tree.

Follow-up Questions

  1. What if equal values were allowed in the left subtree? An upper bound always comes from turning left, so reject only when val > high (and still when val <= low). The inorder check alone can no longer tell [2,2] (valid) from [2,null,2] (invalid), so use the bounds version.
  2. Can you do it in O(1) extra space? Morris inorder traversal threads the tree temporarily and compares consecutive values without a stack, restoring the tree afterwards.
  3. Find the two nodes that were swapped in a BST (LeetCode 99). Use the inorder walk and record where the sequence decreases.
  4. Find the largest subtree that is a valid BST (LeetCode 333). Post-order: each subtree returns its size, min, max and validity.
  5. Validate a BST given only its preorder sequence (LeetCode 255). Use a monotonic stack that tracks the current lower bound.