BST Insertion — How Binary Search Tree Insert Works

How BST Insertion Works

Insertion into a Binary Search Tree (BST) follows a simple recursive rule: compare the new value to the current node, go left if smaller, go right if larger, and create a new leaf node when you reach a null position.

The Algorithm

INSERT(root, value):
  if root is NULL:
    return new Node(value)
  if value < root.value:
    root.left = INSERT(root.left, value)
  else if value > root.value:
    root.right = INSERT(root.right, value)
  return root   // duplicates ignored

Step-by-Step Example

Consider inserting the sequence [8, 3, 10, 1, 6, 14, 4, 7] into an empty BST:

1. 8 becomes the root
2. 3 < 8 — goes left of 8
3. 10 > 8 — goes right of 8
4. 1 < 8, 1 < 3 — goes left of 3
5. 6 < 8, 6 > 3 — goes right of 3
6. 14 > 8, 14 > 10 — goes right of 10
7. 4 < 8, 4 > 3, 4 < 6 — goes left of 6
8. 7 < 8, 7 > 3, 7 > 6 — goes right of 6

Time Complexity

• Average case: O(log n) when the tree is reasonably balanced
• Worst case: O(n) when inserting sorted data creates a linked-list-shaped tree
• The order of insertion directly determines the tree shape

Important Properties

The BST invariant must hold after every insertion: for any node, all values in the left subtree are strictly less, and all values in the right subtree are strictly greater. Duplicate values are typically either ignored or handled with a count field on each node.

Insertion Order Matters

Inserting [1, 2, 3, 4, 5] produces a degenerate right-skewed tree (height 5). Inserting [3, 1, 5, 2, 4] produces a balanced tree (height 3). The same set of values can produce very different tree shapes depending on insertion order, which directly affects lookup performance.