deepSWE.io

Validate Binary Search Tree

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 subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1: Valid BST

Output: true

Example 2: Invalid BST

Output: false

Solution (DFS with Range)

The solution uses a recursive Depth-First Search (DFS) approach to validate the tree. We traverse the tree, keeping track of the valid range (min and max) for each node's value.

Algorithm Steps

The base case for the recursion is when a node is null, which is a valid BST, so we return true.
For each node, check if its value is within the valid range (min < node.val < max).
Recursively call the function for the left child, updating the max value to the current node's value.
Recursively call the function for the right child, updating the min value to the current node's value.
If all nodes satisfy the BST property, the tree is a valid BST.

Start: Validate the tree.

Validate Binary Search Tree Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, low=-float('inf'), high=float('inf')):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))
        
        return validate(root)