Validate Binary Search Tree#

Problem#

Given the root of a binary tree, decide whether it is a valid binary search tree. A valid BST requires every node’s value to be greater than all values in its left subtree and less than all values in its right subtree, and both subtrees must themselves be valid BSTs.

Example#

The tree 2 -> (1, 3) is a valid BST, so the answer is True. The tree 5 -> (1, 4 -> (3, 6)) is invalid because 3 sits in the right subtree of 5 yet is smaller than 5, so the answer is False.

Brute force pitfall#

A common wrong attempt only checks each node against its immediate children. That fails the second example, because a deep descendant can violate an ancestor’s bound. You must carry the allowed range down the tree.

Optimal approach#

Recurse with an open interval (low, high) that each node’s value must fall inside. The root starts with an unbounded range. Going left tightens the upper bound to the current value; going right tightens the lower bound. If any node falls outside its allowed range, the tree is not a BST. This checks the full subtree constraint in a single traversal.

Solution#

 1class TreeNode:
 2    def __init__(self, val=0, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7
 8def is_valid_bst(root: TreeNode | None) -> bool:
 9    def check(node, low, high):
10        if node is None:
11            return True
12        if not (low < node.val < high):
13            return False
14        return check(node.left, low, node.val) and \
15            check(node.right, node.val, high)
16
17    return check(root, float("-inf"), float("inf"))
18
19
20valid = TreeNode(2, TreeNode(1), TreeNode(3))
21print(is_valid_bst(valid))  # True
22
23invalid = TreeNode(5, TreeNode(1),
24                      TreeNode(4, TreeNode(3), TreeNode(6)))
25print(is_valid_bst(invalid))  # False

Complexity#

• Time: O(n), one visit per node.
• Space: O(h) for the recursion stack.

Deepen your BST skills in the trees topic, then continue the 60-day challenge.