98. Validate Binary Search Tree

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/validate-binary-search-tree
• topics: Binary Search, Tree

Description

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.

Idea

• in-order traversal retrieves the keys in ascending sorted order
• We may also solve it using recursion and left/right limits

Code

Inorder traversal

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Initialize the previous value to negative infinity
        previous_value = float('-inf')
        is_valid = True
 
        def inorder_traversal(node):
            nonlocal previous_value, is_valid
            # Exit early if the BST condition has already failed
            if not is_valid:
                return
 
            # Traverse the left subtree
            if node.left:
                inorder_traversal(node.left)
 
            # Check if the current node violates the BST property
            if previous_value >= node.val:
                is_valid = False
                return
                
            # Update the previous value to the current node's value
            previous_value = node.val
 
            # Traverse the right subtree
            if node.right:
                inorder_traversal(node.right)
 
        # Start the in-order traversal from the root
        inorder_traversal(root)
 
        return is_valid

Recursion with left and right limits

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Initialize the previous value to negative infinity
        previous_value = float('-inf')
        is_valid = True
 
        def inorder_traversal(node):
            nonlocal previous_value, is_valid
            # Exit early if the BST condition has already failed
            if not is_valid:
                return
 
            # Traverse the left subtree
            if node.left:
                inorder_traversal(node.left)
 
            # Check if the current node violates the BST property
            if previous_value >= node.val:
                is_valid = False
                return
                
            # Update the previous value to the current node's value
            previous_value = node.val
 
            # Traverse the right subtree
            if node.right:
                inorder_traversal(node.right)
 
        # Start the in-order traversal from the root
        inorder_traversal(root)
 
        return is_valid