Insert into a Binary Search Tree
Descend by comparison until a null child, then attach a new leaf there
A BST has exactly one valid leaf position for any new key: follow the same left/right comparisons a search would, and the walk falls off the tree at precisely the spot where the new node belongs. No existing node ever needs to move or rotate — insertion only ever adds a new leaf. Recursively, each call reattaches its child pointer to whatever the deeper call returns, so the update propagates back up to the root.
Details
Animated on: root = [4, 2, 7, 1, 3], val = 5 — insert 5 into this BST and return the updated root. Expected: 5 becomes the left child of 7.
Problem:Insert into a Binary Search TreeMedium
Descend by comparison until a null child, then attach a new leaf there
step 1 / 10
Call stack
Enter node 4. Compare 5 against it to pick a side.
1FUNCTION insert(node, val):2 IF node = null: RETURN Node(val)3 IF val < node.val:4 node.left <- insert(node.left, val)5 ELSE IF val > node.val:6 node.right <- insert(node.right, val)7 RETURN node
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- Enter node 4. Compare 5 against it to pick a side.
- 5 > 4, so 5 belongs somewhere in 4's right subtree.
- Enter node 7. Compare 5 against it to pick a side.
- 5 < 7, so 5 belongs somewhere in 7's left subtree.
- This child slot is null — that is the insertion point. Create Node(5) here.
- Back at 7: its left pointer now targets whatever the recursive call returned.
- insert(7, 5) returns 7 — same node identity, only the subtree beneath it grew.
- Back at 4: its right pointer now targets whatever the recursive call returned.
- insert(4, 5) returns 4 — same node identity, only the subtree beneath it grew.
- Insertion complete. 5 is now the left child of 7, and the BST ordering property holds everywhere.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.