98. 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.

You can refer sample examples on following link.

Q. Valid 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 helper(self, root, left, right):
        if root == None:
            return True
        
        # 1. make sure current root node has value less than immediate parent
        # 2. make sure current root node has value greater than immediate parent
        # 3. Make sure current root node has value greater or less than top root node
        # depending current node exist in left or right subtree
        
        if root.val >= right or root.val <= left:
            return False
        
        return self.helper(root.left, left, root.val) and self.helper(root.right, root.val, right)
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        min_num = -math.inf
        max_num = math.inf
        return self.helper(root, min_num, max_num)

Visual understanding using example:

For more such readable code and visual diagram in python. Please follow me.

If you find any questions difficult to understand and need such readable code and diagram, please DM me your question at @punitvara twitter account. I will do it with very minimal amount.