98. Validate Binary Search Tree - Explanation

Description

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

A valid binary search tree satisfies the following constraints:

The left subtree of every node contains only nodes with keys less than the node's key.
The right subtree of every node contains only nodes with keys greater than the node's key.
Both the left and right subtrees are also binary search trees.

Example 1:

Input: root = [2,1,3]

Output: true

Example 2:

Input: root = [1,2,3]

Output: false

Explanation: The root node's value is 1 but its left child's value is 2 which is greater than 1.

Constraints:

1 <= The number of nodes in the tree <= 1000.
-1000 <= Node.val <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

A brute force solution would involve traversing the tree and, for every node, checking its entire left subtree to ensure all nodes are less than the current node, and its entire right subtree to ensure all nodes are greater. This results in an O(n^2) solution. Can you think of a better way? Maybe tracking values during the traversal would help.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. At each node, we need to ensure that the tree rooted at that node is a valid Binary Search Tree (BST). One way to do this is by tracking an interval that defines the lower and upper limits for the node's value in that subtree. This interval will be updated as we move down the tree, ensuring each node adheres to the BST property.

Hint 3

We start with the interval [-infinity, infinity] for the root node. As we traverse the tree, when checking the left subtree, we update the maximum value limit because all values in the left subtree must be less than the current node's value. Conversely, when checking the right subtree, we update the minimum value limit because all values in the right subtree must be greater than the current node's value.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search Tree Properties - Understanding that left subtree values must be less than the node and right subtree values must be greater
Tree Traversal (DFS/BFS) - Navigating through tree nodes using depth-first or breadth-first approaches
Recursion - Passing constraints (valid ranges) down through recursive calls

1. Brute Force

Intuition

To check if a tree is a valid Binary Search Tree (BST), every node must satisfy:

All values in its left subtree are strictly less than the node’s value.
All values in its right subtree are strictly greater than the node’s value.

In this brute force idea, for each node we:

Check all nodes in its left subtree to confirm they are < node.val.
Check all nodes in its right subtree to confirm they are > node.val.
Then recursively repeat the same process for each child as a new root.

This re-checks many nodes multiple times, so it’s correct but not efficient.

Algorithm

If the tree is empty → return true.
For the current node:
- Run a helper on its left subtree to ensure every value < current value.
- Run a helper on its right subtree to ensure every value > current value.
- If either check fails → return false.
Recursively:
- Check that the left child's subtree is a valid BST.
- Check that the right child's subtree is a valid BST.
If all checks pass for every node → return true.

# 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

class Solution:
    left_check = staticmethod(lambda val, limit: val < limit)
    right_check = staticmethod(lambda val, limit: val > limit)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        if (not self.isValid(root.left, root.val, self.left_check) or
            not self.isValid(root.right, root.val, self.right_check)):
            return False

        return self.isValidBST(root.left) and self.isValidBST(root.right)

    def isValid(self, root: Optional[TreeNode], limit: int, check) -> bool:
        if not root:
            return True
        if not check(root.val, limit):
            return False
        return (self.isValid(root.left, limit, check) and
                self.isValid(root.right, limit, check))

/**
 * 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;
 *     }
 * }
 */

public class Solution {
    static boolean left_check(int val, int limit) {
        return val < limit;
    }

    static boolean right_check(int val, int limit) {
        return val > limit;
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValid(root.left, root.val, Solution::left_check) ||
            !isValid(root.right, root.val, Solution::right_check)) {
            return false;
        }

        return isValidBST(root.left) && isValidBST(root.right);
    }

    public boolean isValid(TreeNode root, int limit, CheckFunction check) {
        if (root == null) {
            return true;
        }
        if (!check.apply(root.val, limit)) {
            return false;
        }
        return isValid(root.left, limit, check) &&
               isValid(root.right, limit, check);
    }

    interface CheckFunction {
        boolean apply(int val, int limit);
    }
}

/**
 * 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) {}
 * };
 */

class Solution {
public:
    static bool left_check(int val, int limit) {
        return val < limit;
    }

    static bool right_check(int val, int limit) {
        return val > limit;
    }

    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }

        if (!isValid(root->left, root->val, left_check) ||
            !isValid(root->right, root->val, right_check)) {
            return false;
        }

        return isValidBST(root->left) && isValidBST(root->right);
    }

    bool isValid(TreeNode* root, int limit, bool (*check)(int, int)) {
        if (!root) {
            return true;
        }
        if (!check(root->val, limit)) {
            return false;
        }
        return isValid(root->left, limit, check) &&
               isValid(root->right, limit, check);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {number} val
     * @param {number} limit
     * @returns {boolean}
     */
    left_check(val, limit) {
        return val < limit;
    }

    /**
     * @param {number} val
     * @param {number} limit
     * @returns {boolean}
     */
    right_check(val, limit) {
        return val > limit;
    }

    /**
     * @param {TreeNode} root
     * @returns {boolean}
     */
    isValidBST(root) {
        if (!root) {
            return true;
        }

        if (
            !this.isValid(root.left, root.val, this.left_check) ||
            !this.isValid(root.right, root.val, this.right_check)
        ) {
            return false;
        }

        return this.isValidBST(root.left) && this.isValidBST(root.right);
    }

    /**
     * @param {TreeNode} root
     * @param {number} limit
     * @param {function} check
     * @returns {boolean}
     */
    isValid(root, limit, check) {
        if (!root) {
            return true;
        }
        if (!check.call(this, root.val, limit)) {
            return false;
        }
        return (
            this.isValid(root.left, limit, check) &&
            this.isValid(root.right, limit, check)
        );
    }
}

/**
 * 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;
 *     }
 * }
 */

public class Solution {
    static bool LeftCheck(int val, int limit) {
        return val < limit;
    }

    static bool RightCheck(int val, int limit) {
        return val > limit;
    }

    public bool IsValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!IsValid(root.left, root.val, LeftCheck) ||
            !IsValid(root.right, root.val, RightCheck)) {
            return false;
        }

        return IsValidBST(root.left) && IsValidBST(root.right);
    }

    public bool IsValid(TreeNode root, int limit, Func<int, int, bool> check) {
        if (root == null) {
            return true;
        }
        if (!check(root.val, limit)) {
            return false;
        }
        return IsValid(root.left, limit, check) &&
               IsValid(root.right, limit, check);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isValid(root.Left, root.Val, func(val, limit int) bool { return val < limit }) &&
           isValid(root.Right, root.Val, func(val, limit int) bool { return val > limit }) &&
           isValidBST(root.Left) &&
           isValidBST(root.Right)
}

func isValid(root *TreeNode, limit int, check func(int, int) bool) bool {
    if root == nil {
        return true
    }
    if !check(root.Val, limit) {
        return false
    }
    return isValid(root.Left, limit, check) && isValid(root.Right, limit, check)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private val leftCheck: (Int, Int) -> Boolean = { value, limit -> value < limit }
    private val rightCheck: (Int, Int) -> Boolean = { value, limit -> value > limit }

    fun isValidBST(root: TreeNode?): Boolean {
        if (root == null) return true
        if (!isValid(root.left, root.`val`, leftCheck) || !isValid(root.right, root.`val`, rightCheck)) {
            return false
        }
        return isValidBST(root.left) && isValidBST(root.right)
    }

    private fun isValid(root: TreeNode?, limit: Int, check: (Int, Int) -> Boolean): Boolean {
        if (root == null) return true
        if (!check(root.`val`, limit)) return false
        return isValid(root.left, limit, check) && isValid(root.right, limit, check)
    }
}

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        if !isValid(root.left, root.val, { $0 < $1 }) ||
           !isValid(root.right, root.val, { $0 > $1 }) {
            return false
        }

        return isValidBST(root.left) && isValidBST(root.right)
    }

    private func isValid(_ root: TreeNode?, _ limit: Int, _ check: (Int, Int) -> Bool) -> Bool {
        guard let root = root else { return true }
        if !check(root.val, limit) {
            return false
        }

        return isValid(root.left, limit, check) && isValid(root.right, limit, check)
    }
}

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn is_valid(
            node: &Option<Rc<RefCell<TreeNode>>>,
            limit: i32,
            check: fn(i32, i32) -> bool,
        ) -> bool {
            match node {
                None => true,
                Some(n) => {
                    let n = n.borrow();
                    if !check(n.val, limit) {
                        return false;
                    }
                    is_valid(&n.left, limit, check)
                        && is_valid(&n.right, limit, check)
                }
            }
        }

        fn validate(node: &Option<Rc<RefCell<TreeNode>>>) -> bool {
            match node {
                None => true,
                Some(n) => {
                    let n = n.borrow();
                    is_valid(&n.left, n.val, |v, l| v < l)
                        && is_valid(&n.right, n.val, |v, l| v > l)
                        && validate(&n.left)
                        && validate(&n.right)
                }
            }
        }

        validate(&root)
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Depth First Search

Intuition

A Binary Search Tree isn’t just about each node being smaller or larger than its parent —
every node must fit within a valid value range decided by all its ancestors.

For the root, the allowed range is (-∞, +∞).
When you go left, the node’s value must be less than the parent, so the upper bound becomes smaller.
When you go right, the node’s value must be greater than the parent, so the lower bound becomes larger.

As we move down the tree, we keep tightening these bounds.
If any node violates its allowed range → the tree is not a BST.

This checks all BST rules efficiently in one DFS pass.

Algorithm

Start DFS from the root with the initial valid range (-∞, +∞).
For each node:
- If node.val is not strictly between (left, right) → return false.
Recursively:
- Validate the left subtree with updated range (left, node.val).
- Validate the right subtree with updated range (node.val, right).
If all nodes satisfy their ranges → it is a valid BST.

# 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

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, left, right):
            if not node:
                return True
            if not (left < node.val < right):
                return False

            return valid(node.left, left, node.val) and valid(
                node.right, node.val, right
            )

        return valid(root, float("-inf"), float("inf"))

/**
 * 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;
 *     }
 * }
 */

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

    public boolean valid(TreeNode node, long left, long right) {
        if (node == null) {
            return true;
        }
        if (!(left < node.val && node.val < right)) {
            return false;
        }
        return valid(node.left, left, node.val) &&
               valid(node.right, node.val, right);
    }
}

/**
 * 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) {}
 * };
 */

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return valid(root, LONG_MIN, LONG_MAX);
    }

    bool valid(TreeNode* node, long left, long right) {
        if (!node) {
            return true;
        }
        if (!(left < node->val && node->val < right)) {
            return false;
        }
        return valid(node->left, left, node->val) &&
               valid(node->right, node->val, right);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    isValidBST(root) {
        return this.valid(root, -Infinity, Infinity);
    }

    /**
     * @param {TreeNode} node
     * @param {number} left
     * @param {number} right
     */
    valid(node, left, right) {
        if (node === null) {
            return true;
        }
        if (!(left < node.val && node.val < right)) {
            return false;
        }
        return (
            this.valid(node.left, left, node.val) &&
            this.valid(node.right, node.val, right)
        );
    }
}

/**
 * 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;
 *     }
 * }
 */

public class Solution {
    public bool IsValidBST(TreeNode root) {
        return valid(root, long.MinValue, long.MaxValue);
    }

    public bool valid(TreeNode node, long left, long right) {
        if (node == null) {
            return true;
        }
        if (!(left < node.val && node.val < right)) {
            return false;
        }
        return valid(node.left, left, node.val) &&
               valid(node.right, node.val, right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return valid(root, math.MinInt64, math.MaxInt64)
}

func valid(node *TreeNode, left, right int64) bool {
    if node == nil {
        return true
    }

    val := int64(node.Val)
    if val <= left || val >= right {
        return false
    }

    return valid(node.Left, left, val) && valid(node.Right, val, right)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }

    private fun valid(node: TreeNode?, left: Long, right: Long): Boolean {
        if (node == null) {
            return true
        }

        val value = node.`val`.toLong()
        if (value <= left || value >= right) {
            return false
        }

        return valid(node.left, left, value) &&
               valid(node.right, value, right)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        return valid(root, Int.min, Int.max)
    }

    private func valid(_ node: TreeNode?, _ left: Int, _ right: Int) -> Bool {
        guard let node = node else { return true }
        if !(left < node.val && node.val < right) {
            return false
        }
        return valid(node.left, left, node.val) && valid(node.right, node.val, right)
    }
}

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn valid(node: &Option<Rc<RefCell<TreeNode>>>, left: i64, right: i64) -> bool {
            match node {
                None => true,
                Some(n) => {
                    let n = n.borrow();
                    let val = n.val as i64;
                    if val <= left || val >= right {
                        return false;
                    }
                    valid(&n.left, left, val) && valid(&n.right, val, right)
                }
            }
        }

        valid(&root, i64::MIN, i64::MAX)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Breadth First Search

Intuition

A tree is a valid BST only if every node lies within a valid range defined by its ancestors.
Instead of using recursion, we can use a queue (BFS) to check this level by level.

Start with the root, whose valid range is (-∞, +∞).
When moving to the left child, its maximum allowed value becomes the current node’s value.
When moving to the right child, its minimum allowed value becomes the current node’s value.
If any node violates its allowed range, the tree is not a BST.

This way, we verify every node exactly once using BFS.

Algorithm

If the tree is empty → return true.
Push (root, -∞, +∞) into a queue.
While the queue is not empty:
- Pop (node, leftBound, rightBound).
- If node.val is not between (leftBound, rightBound), return false.
- Push the left child with range (leftBound, node.val).
- Push the right child with range (node.val, rightBound).
If all nodes satisfy their ranges → return true.

# 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

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        q = deque([(root, float("-inf"), float("inf"))])

        while q:
            node, left, right = q.popleft()
            if not (left < node.val < right):
                return False
            if node.left:
                q.append((node.left, left, node.val))
            if node.right:
                q.append((node.right, node.val, right))

        return True

/**
 * 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;
 *     }
 * }
 */

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, Long.MIN_VALUE, Long.MAX_VALUE});

        while (!queue.isEmpty()) {
            Object[] current = queue.poll();
            TreeNode node = (TreeNode) current[0];
            long left = (long) current[1];
            long right = (long) current[2];

            if (!(left < node.val && node.val < right)) {
                return false;
            }

            if (node.left != null) {
                queue.offer(new Object[]{node.left, left, (long) node.val});
            }
            if (node.right != null) {
                queue.offer(new Object[]{node.right, (long) node.val, right});
            }
        }

        return true;
    }
}

/**
 * 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) {}
 * };
 */

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }

        queue<tuple<TreeNode*, long, long>> queue;
        queue.push(make_tuple(root, LONG_MIN, LONG_MAX));

        while (!queue.empty()) {
            auto [node, left, right] = queue.front();
            queue.pop();

            if (!(left < node->val && node->val < right)) {
                return false;
            }
            if (node->left) {
                queue.push(make_tuple(node->left, left, node->val));
            }
            if (node->right) {
                queue.push(make_tuple(node->right, node->val, right));
            }
        }

        return true;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    /**
     * @param {TreeNode} root
     * @return {boolean}
     */
    isValidBST(root) {
        if (root === null) {
            return true;
        }

        const queue = new Queue([[root, -Infinity, Infinity]]);

        while (queue.size() > 0) {
            const [node, left, right] = queue.pop();

            if (!(left < node.val && node.val < right)) {
                return false;
            }
            if (node.left) {
                queue.push([node.left, left, node.val]);
            }
            if (node.right) {
                queue.push([node.right, node.val, right]);
            }
        }

        return true;
    }
}

/**
 * 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;
 *     }
 * }
 */

public class Solution {
    public bool IsValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<(TreeNode node, long left, long right)> queue = new Queue<(TreeNode, long, long)>();
        queue.Enqueue((root, long.MinValue, long.MaxValue));

        while (queue.Count > 0) {
            var (node, left, right) = queue.Dequeue();

            if (!(left < node.val && node.val < right)) {
                return false;
            }
            if (node.left != null) {
                queue.Enqueue((node.left, left, node.val));
            }
            if (node.right != null) {
                queue.Enqueue((node.right, node.val, right));
            }
        }

        return true;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type QueueItem struct {
    node *TreeNode
    left int64
    right int64
}

func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true
    }

    queue := []QueueItem{{root, math.MinInt64, math.MaxInt64}}

    for len(queue) > 0 {
        item := queue[0]
        queue = queue[1:]

        val := int64(item.node.Val)
        if val <= item.left || val >= item.right {
            return false
        }

        if item.node.Left != nil {
            queue = append(queue, QueueItem{item.node.Left, item.left, val})
        }
        if item.node.Right != nil {
            queue = append(queue, QueueItem{item.node.Right, val, item.right})
        }
    }

    return true
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private data class QueueItem(
        val node: TreeNode,
        val left: Long,
        val right: Long
    )

    fun isValidBST(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }

        val queue = ArrayDeque<QueueItem>()
        queue.addLast(QueueItem(root, Long.MIN_VALUE, Long.MAX_VALUE))

        while (queue.isNotEmpty()) {
            val (node, left, right) = queue.removeFirst()

            val value = node.`val`.toLong()
            if (value <= left || value >= right) {
                return false
            }

            node.left?.let {
                queue.addLast(QueueItem(it, left, value))
            }
            node.right?.let {
                queue.addLast(QueueItem(it, value, right))
            }
        }

        return true
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }

        var q = Deque<(TreeNode, Int, Int)>()
        q.append((root, Int.min, Int.max))

        while !q.isEmpty {
            let (node, left, right) = q.popFirst()!

            if !(left < node.val && node.val < right) {
                return false
            }

            if let leftNode = node.left {
                q.append((leftNode, left, node.val))
            }
            if let rightNode = node.right {
                q.append((rightNode, node.val, right))
            }
        }
        return true
    }
}

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        if root.is_none() {
            return true;
        }

        let mut queue = VecDeque::new();
        queue.push_back((root.clone().unwrap(), i64::MIN, i64::MAX));

        while let Some((node, left, right)) = queue.pop_front() {
            let node = node.borrow();
            let val = node.val as i64;
            if val <= left || val >= right {
                return false;
            }
            if let Some(ref l) = node.left {
                queue.push_back((Rc::clone(l), left, val));
            }
            if let Some(ref r) = node.right {
                queue.push_back((Rc::clone(r), val, right));
            }
        }

        true
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Only Comparing with the Immediate Parent

A classic mistake is checking only that left.val < node.val < right.val for direct children. This misses cases where a node deep in the left subtree has a value greater than an ancestor. For example, a tree with root 10, left child 5, and right grandchild 15 under node 5 would pass local checks but violates BST properties. The valid range must be inherited from all ancestors.

Using Inclusive Bounds Instead of Exclusive

BST properties require strictly less than and strictly greater than comparisons. Using <= or >= instead of < and > will incorrectly accept trees with duplicate values, which violates the standard BST definition where all left descendants are strictly less and all right descendants are strictly greater.

Integer Overflow with Boundary Values

When using Integer.MIN_VALUE and Integer.MAX_VALUE as initial bounds, problems arise if the tree contains these exact values as node data. The comparison node.val > Integer.MAX_VALUE will never be true. Use Long.MIN_VALUE and Long.MAX_VALUE or nullable types to handle edge cases where node values equal the integer limits.