BST Insertion

Insertion finds where the new value belongs, then creates a node:

def insert(root, val):
    if root == null:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

The search path determines the insertion point. New nodes always become leaves.

Time: $O(h)$. Space: $O(h)$ for recursion.

Notice that insertion order determines tree shape. Inserting $[3, 1, 5, 2, 4]$ gives a balanced tree. Inserting $[1, 2, 3, 4, 5]$ gives a right-skewed stick.

That's why balanced BST variants (AVL, Red-Black) rebalance after insertions.