LeetCode 98 - Validate Binary Search Tree

This is a Medium BST validation problem. Given the root of a binary tree, we need to decide whether the entire tree is a valid binary search tree. The solution I used passes the allowed lower and upper bounds down the recursion for each node.

Problem link and explanation

Problem link: 98. Validate Binary Search Tree
Summary: Given the root of a binary tree, return true if every node satisfies the BST rule, and false if any node breaks it.

In a BST, every value in the left subtree must be smaller than the current node, and every value in the right subtree must be larger. The important part is that checking only the immediate children is not enough.

For example, consider this tree.

If we only look at node 7, its left child 4 is smaller than 7, so that part looks valid. But 4 is inside the right subtree of the root 5, so it also has to be larger than 5. Since 4 is smaller than 5, this tree is not a valid BST.

So the problem is not just parent-child comparison. Each node has to stay inside the full range imposed by all of its ancestors.

Approach

The first approach that comes to mind is to compare each node only with its direct children.

left.val < node.val < right.val

But this is only a local check. The BST rule is a constraint over the whole subtree. Every node in the left subtree must be smaller than the current node, and every node in the right subtree must be larger.

So I passed the allowed range into each recursive call. At the root, any value is allowed, so the initial lower bound is negative infinity and the upper bound is positive infinity.

lower = -inf
upper = inf

If the current node value falls outside that range, the tree is invalid.

if node.val <= lower or node.val >= upper:
    return False

When moving to the left child, the current node value becomes the new upper bound because every value in the left subtree must be smaller than the current node.

left range: lower < value < node.val

When moving to the right child, the current node value becomes the new lower bound.

right range: node.val < value < upper

With this setup, each node is checked against all ancestor constraints, not only against its direct parent.

Troubleshooting

The common mistake in this problem is checking only the immediate children. For example, we might write code that only verifies whether the left child is smaller and the right child is larger.

if node.left and node.left.val >= node.val:
    return False
if node.right and node.right.val <= node.val:
    return False

That code fails on this tree.

The value 4 satisfies the local rule under node 7 because it is smaller than 7. But it violates the range inherited from node 5 because it appears in the right subtree of 5 and should be greater than 5. If we compare only with the direct parent, we lose the ancestor constraints.

That is why each recursive call needs to know the current valid range. Once we move to the right of the root, every node below that point must be greater than the root value. If we then move left under another node, the value also has to be smaller than that parent. Each node is not checked against one value. It is checked against lower and upper.

Another detail is duplicate values. LeetCode defines a valid BST using strictly less for the left subtree and strictly greater for the right subtree. Equal values are not allowed.

if node.val <= lower or node.val >= upper:
    return False

That is why the comparisons include equality. A value equal to lower or upper is invalid.

One small Python detail: min and max are built-in function names. The code can still run if they are used as parameter names, but it shadows the built-ins. In the final version, I used lower and upper instead.

Complexity analysis

Time complexity: O(n)
- Each node is visited at most once. The function may return earlier when it finds an invalid node, but in the worst case it has to inspect the whole tree.
Space complexity: O(h)
- The recursive call stack grows with the height of the tree. For a balanced tree, the height is O(log n). For a skewed tree, it can grow to O(n).

Here, n is the number of nodes, and h is the height of the tree.

Implementation code

The final code uses DFS and updates the valid value range as it moves down the tree.

from typing import Optional

class Solution:
    def solve(self, node: Optional[TreeNode], lower: float, upper: float) -> bool:
        if node is None:
            return True

        if node.val <= lower or node.val >= upper:
            return False

        left = self.solve(node.left, lower, node.val)
        right = self.solve(node.right, node.val, upper)
        return left and right

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.solve(root, float('-inf'), float('inf'))

If we want to stop a little earlier, we can return directly so the right subtree is not checked after the left subtree has already failed.

from typing import Optional

class Solution:
    def solve(self, node: Optional[TreeNode], lower: float, upper: float) -> bool:
        if node is None:
            return True

        if node.val <= lower or node.val >= upper:
            return False

        return (
            self.solve(node.left, lower, node.val)
            and self.solve(node.right, node.val, upper)
        )

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self.solve(root, float('-inf'), float('inf'))

Both versions have the same Big-O complexity, but the second version skips the remaining check once the result is already false. If the left subtree is invalid, there is no need to call the right subtree.

Summary and reflection

BST validation can fail if we only compare a node with its direct children. Each node has to satisfy the lower and upper bounds created while moving down from the root.

When we move left, the current value becomes the new upper bound. When we move right, the current value becomes the new lower bound. Passing that range through recursion keeps the ancestor constraints intact.

The main point of this problem was not the tree traversal itself. It was deciding what state the recursion needs to carry. Once the BST rule is represented as lower and upper bounds, the cases missed by local comparison become straightforward to catch.