98. Validate Binary Search Tree

Problem Statement in English

You’re given the root of a binary tree. You need to determine if it is a valid binary search tree (BST).

Approach

We can solve this by passing the constraints for each node as we traverse the tree. For each node, we check if its value is within the valid range defined by its ancestors.

If every node is valid then the tree is a valid BST, otherwise we return False.

For the initial kickoff of the recursion, we can use negative infinity and positive infinity as the range constraints.

And we’re done!

Solution in Python

class Solution:
    def isValidBST(self, root: TreeNode | None) -> bool:
        def solve(node, start, end):
            if not node: return True

            if not (start < node.val < end): return False

            return solve(node.left, start, node.val) and solve(node.right, node.val, end)

        return solve(root, -inf, inf)

Complexity

• Time: $O(n)$
  Since we are visiting each node once, the time complexity is linear with respect to the number of nodes in the tree.

• Space: $O(h)$
  Since we are using recursion, the space complexity is proportional to the height of the tree, which can be up to $O(n)$ in the worst case (for a skewed tree) and $O(log n)$ for a balanced tree.

And we are done.