Insertion — O(log n) average

def insert(root, key):
    if not root:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

Search — O(log n) average

Start at root, go left if target < current, right if target > current.

Traversals

• In-order (Left, Root, Right): gives sorted output
• Pre-order (Root, Left, Right): useful for copying
• Post-order (Le