Binary Search Tree

A Binary Search Tree (BST) is a tree where every node follows one rule: left children are smaller, right children are larger. This simple property gives you O(log n) search, insert, and delete - when the tree is balanced.

The BST Property

For every node: all values in its left subtree are smaller, all values in its right subtree are larger. This ordering makes search efficient - you always know which way to go.

Classic: Validate BST

The trick: each node must be within a valid range.

def isValidBST(root):
    def validate(node, min_val, max_val):
        if not node:
            return True

        if node.val <= min_val or node.val >= max_val:
            return False

        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

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

Classic: Kth Smallest Element

Use inorder traversal - it visits nodes in sorted order:

def kthSmallest(root, k):
    stack = []
    current = root

    while stack or current:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val

        current = current.right