Validate Binary Search Tree

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.

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

Approach

Validate the tree with DFS and value bounds. Each node must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree, so pass down (low, high) limits during recursion. An empty tree is valid.

Why It Works

The BST property is global, not just local to children. Maintaining bounds ensures every node respects the constraints imposed by all its ancestors. If any node violates the range, the tree is invalid; otherwise it is valid.

Complexity

• Time: O(n)
• Space: O(h)

Reference Implementation (Python)

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

        return dfs(root, float('-inf'), float('inf'))