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.

Additional information

• The number of nodes in the tree is in the range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

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. Also, the node with value 3 is in the right subtree of 5, but 3 < 5.

Example 3:

Input: root = [2, 2, 2]

Output: false

Explanation: The left and right children must be strictly less than and strictly greater than the root, respectively.

Recursive DFS (Valid Boundaries) - Optimal

Intuition

A common mistake is to only check if a node is greater than its left child and less than its right child. However, a valid BST requires that all nodes in the entire left subtree are less than the root, and all nodes in the entire right subtree are greater than the root.

To enforce this, we can traverse the tree using Depth-First Search (DFS) while passing down a valid "range" or boundary (low, high) for each node.

• When we go to the left child, the upper bound is updated to the current node's value.
• When we go to the right child, the lower bound is updated to the current node's value.

Algorithm

1. Create a helper function validate(node, low, high).
2. Base Case: If node is None, return True (an empty tree is a valid BST).
3. Boundary Check: If node.val <= low or node.val >= high, return False (the node violates the BST property).
4. Recurse: Check both subtrees:

• For the left subtree, call validate(node.left, low, node.val).
• For the right subtree, call validate(node.right, node.val, high).

5. Return True only if both recursive calls return True.
6. Call the helper function starting with the root and absolute infinity boundaries: validate(root, -float('inf'), float('inf')).

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    def validate(node, low=-float('inf'), high=float('inf')):
        if not node:
            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)

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the binary tree exactly once.

• Space complexity: O(h)

• Reason: The space complexity is determined by the maximum depth of the recursion stack, which is the height h of the tree. In the worst case (a skewed tree), it is O(n). In the best case (a balanced tree), it is O(log n).

Iterative Inorder Traversal

Intuition

An inherent property of a valid Binary Search Tree is that an Inorder Traversal (Left -> Node -> Right) will process the nodes in strictly ascending order. We can perform an iterative inorder traversal using a stack and keep track of the previously visited node's value. If we ever encounter a node whose value is less than or equal to the previous value, the tree is not a valid BST.

Algorithm

1. Initialize a stack and set a curr pointer to root.
2. Initialize a variable prev_val to negative infinity (-float('inf')).
3. While curr is not None or the stack is not empty:

• Drill down to the leftmost node, pushing each node onto the stack.
• Pop a node from the stack.
• Check if node.val <= prev_val. If it is, return False.
• Update prev_val = node.val.
• Move curr to the node.right to process the right subtree.

4. If the traversal finishes without any violations, return True.

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    stack = []
    curr = root
    prev_val = -float('inf')
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
            
        curr = stack.pop()
        
        if curr.val <= prev_val:
            return False
            
        prev_val = curr.val
        curr = curr.right
        
    return True

Time & Space Complexity

• Time complexity: O(n)

• Reason: In the worst case, we process every node in the tree once. If the tree is invalid early on, it will short-circuit and run faster.

• Space complexity: O(h)

• Reason: The stack stores at most h nodes at a time, where h is the height of the tree.