Introduction

In this blog post, we will explore how to solve the LeetCode problem "98" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: Input: root = [2,1,3] Output: true Example 2: Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. Constraints: The number of nodes in the tree is in the range [1, 104]. -231 <= Node.val <= 231 - 1

Explanation

Here's a solution to determine if a binary tree is a valid BST:

• In-order Traversal with Validation: Perform an in-order traversal of the binary tree. A valid BST yields an ascending sorted sequence during in-order traversal.
• Maintain Previous Value: Keep track of the previously visited node's value. In each step, check if the current node's value is greater than the previous one. If not, the tree is not a valid BST.

• Handle Empty Tree and First Node: Initialize the previous value to negative infinity to properly handle the first node encountered.

• Runtime Complexity: O(N), where N is the number of nodes in the tree.

• Storage Complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst-case (skewed tree), H = N, leading to O(N) space. In the best-case (balanced tree), H = log N, leading to O(log N) space.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: TreeNode) -> bool:
    """
    Determines if a binary tree is a valid binary search tree (BST).
    """

    def validate(node: TreeNode, low: float, high: float) -> bool:
        """
        Helper function to recursively validate the BST property for each node.
        """
        if node is None:
            return True

        if node.val <= low or node.val >= high:
            return False

        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))

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