Insert into a BST

Insert into a BST is the classic warm-up for binary search trees. It teaches the move that powers every BST operation: at each node, one comparison tells you whether to go left or right, so you reach the right spot in the height of the tree rather than scanning everything.

The slow way first

You could collect every value, append the new one, and rebuild a balanced tree from scratch. That throws away the structure you already have and costs O(n) work plus a full rebuild for a single insert. It also ignores the one thing a BST gives you for free: a built-in compass.

The question to ask: at each node, do I even need to look at both subtrees? No. The BST invariant means a smaller value can only ever live on the left and a larger value only on the right. So one comparison rules out an entire half of the remaining tree.

The idea: walk down comparing, attach at the null

Start at the root. Compare val with the current node. If val is smaller, move into the left child; if larger, move into the right child. Keep walking until the child you want to step into is None — you have fallen off the bottom of the tree. That empty slot is exactly where the new value belongs, so create a leaf there.

The key insight: a new value always lands as a leaf. Walking down never disturbs existing nodes, so the ordering everywhere above the insertion point is automatically preserved.

Walk through it

Step through the animation. The cur pointer walks down the tree. Inserting 6: 6 > 5 so we go right to 8; 6 < 8 so we go left to 7; 6 > 7 so we go right — but 7 has no right child. That None slot is where 6 attaches as a fresh leaf, and the BST order still reads cleanly in-order.

Pseudocode

insert(node, val):
    if node is None:                 # fell off the tree
        return a new leaf holding val
    if val < node.value:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node                      # tree above is unchanged

The Python solution

def insert_into_bst(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

• The base case root is None means we walked off the tree — return a brand-new leaf node, which the caller wires into the empty slot.
• if val < root.val is the single comparison that picks a direction — left for smaller.
• root.left = insert_into_bst(root.left, val) recurses left and re-attaches the (possibly new) subtree. When the recursion returns a fresh leaf, this is the line that links it in.
• The else branch does the mirror move to the right for any value not smaller.
• return root hands back the same node we entered with, so every level above the insertion point is left untouched.

Complexity

The work is proportional to the height of the tree: one comparison per level as we walk down. In a balanced tree that is O(log n); if the tree has degenerated into a chain, it is O(n). The recursion uses O(h) stack space.

When this pattern shows up

Practice