validate-bst

Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

Solution 1: Recursion with Range

def helper(root, lo=-math.inf, hi=math.inf):
    return (
        lo < root.val < hi and
        helper(root.left, lo, root.val) and
        helper(root.right, root.val, hi)
    ) if root else True
 
return helper(root)

Solution 2: Iteration with Range

queue = [(root, -math.inf, math.inf)]
while queue:
    root, lo, hi = queue.pop(0)
    if not lo < root.val < hi:
        return False
    if root.left:
        queue.append((root.left, lo, root.val))
    if root.right:
        queue.append((root.right, root.val, hi))
return True

• Time complexity: $O(N)$, as each node is inserted and popped from the queue once.
• Space complexity: $O(N/2)=O(N)$, the queue is as large as the total number of leaves.

Solution 3: Recursive Inorder Traversal

Utilize the fact that the in-order traversal of a BST is ascending.

traversal = traverse(root)
return len(traversal) <= 1 or eval('<'.join(str(val) for val in traversal))

Alternatively:

return all(x < y for x, y in zip(traversal, traversal[1:]))

Solution 4: Iterative In-Order Traversal

With iteration, we can terminate the iteration once the in-order traversal is not strictly increasing.

stack, prev = [], -math.inf
 
while stack or root:
    while root:
        stack.append(root)
        root = root.left
    root = stack.pop()
    if root.val <= prev:  # the left-most leave is smallest in BST
        return False
    prev = root.val
    root = root.right
return True