98. Validate Binary Search Tree

Summary

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

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

Approach

Recursion.

First approach: We check whether each node satisfies the BST condition by comparing it with its direct children.

If the left subtree and right subtree are valid BSTs, and left.val < root.val < right.val, then it looks valid.

Function

Function validate(root): If root is None: return True is_valid = True If root.left: is_valid = is_valid and root.left.val < root.val If root.right: is_valid = is_valid and root.val < root.right.val return validate(root.left) and validate(root.right) and is_valid

However, this approach is incorrect. For example:

[5,4,6,null,null,3,7]

This algorithm returns True, but the tree is not a valid BST because the right subtree of node 5 contains node 3.

Complexity

Time Complexity: O(N) Space Complexity: O(N) in the worst case because of the recursion stack.

Approach

Recursion.

We pass the current node together with its lower and upper bounds.

If root.val is outside those bounds, return False.

Then recursively check root.left and root.right with updated bounds.

Function

Function validate(root, lower=-inf, upper=inf): If root is None: return True If root.val <= lower or root.val >= upper: return False return validate(root.left, lower, root.val) and validate(root.right, root.val, upper)

Complexity

Time Complexity: O(N) Space Complexity: O(N) in the worst case because of the recursion stack.