BST Insertion —
One comparison finds the spot.
Inserting into a binary search tree is a single walk from the root: smaller goes left, larger goes right, until you find an empty spot. No shifting, no rebalancing in the basic version — just comparisons. Watch the value follow its own path down the tree on LearnBug and see exactly where — and why — it lands.
What is BST Insertion?
Starting at the root, compare the new value to the current node: if smaller, move left; if larger (or equal, by convention), move right. Repeat until you reach an empty spot — a None child — and place the new node there. The path taken is fully determined by comparisons, so there's exactly one correct spot.
Why visualization helps
It's easy to lose track of which node you're "currently at" when reading insertion code, especially the recursive version where the return value threads the new subtree back up. LearnBug highlights the current comparison node at every step, so the left/right decision and the final landing spot are both visible.
Recursive vs iterative — same path, different style
Recursive
Each call returns the (possibly new) subtree root. Clean to read — the tree "rebuilds itself" on the way back up the call stack.
Iterative
Walk down with a pointer, tracking the parent, then attach the new node directly. No call stack growth — O(1) extra space.
Worst case: a skewed tree
Inserting sorted values one after another builds a tree that's really a linked list — every insert becomes O(n), not O(log n).
Insert 5 into 4(2(1,3), 6)
At root 4: is 5 < 4? No — go right
5 is larger than 4, so by BST rules it must live somewhere in the right subtree. Move to node 6.
At node 6: is 5 < 6? Yes — go left
5 is smaller than 6, so it belongs in 6's left subtree. Node 6 currently has no left child.
6.left is empty — insert 5 there
The walk reached a None child, which is exactly the insertion point. A new node holding 5 becomes 6's left child.
Result: 6.left = 5 ✓ tree is now 4(2(1,3), 6(5, None)) — still a valid BST
Recursive and iterative insertion
def insert(node, val):
if node is None:
return Node(val) # found the empty spot
if val < node.val:
node.left = insert(node.left, val)
else:
node.right = insert(node.right, val)
return node # rebuild the path on the way back updef insert_iterative(root, val):
if root is None:
return Node(val)
node = root
while True:
if val < node.val:
if node.left is None:
node.left = Node(val); return root
node = node.left
else:
if node.right is None:
node.right = Node(val); return root
node = node.rightComplexity Notes
Frequently asked questions
What happens if I insert a value that already exists?
It depends on convention. This implementation sends equal values to the right subtree, so duplicates are allowed and always end up to the right of the original. Some BST implementations explicitly reject duplicates by returning early when val == node.val.
Why does insertion order affect the tree's shape?
Each value's path is determined entirely by comparisons against values already in the tree, so the same set of values inserted in a different order can build a completely different (but still valid) BST shape. Inserting already-sorted values, for example, builds a tree that is maximally skewed — effectively a linked list.
How do self-balancing trees fix the O(n) worst case?
Structures like AVL trees and Red-Black trees perform rotations after insertion to keep the height close to log(n) no matter the insertion order, guaranteeing O(log n) insert/search even in the worst case. A plain BST (this lesson) makes no such guarantee.
Recursive or iterative — which should I use?
Functionally identical — same path, same result. Recursive is usually easier to read and reason about; iterative avoids call-stack growth, which matters on very deep/skewed trees where recursion could hit Python's recursion limit.
Watch a value find its own spot in the tree
Paste your BST insertion into LearnBug and see every left/right decision animate.