Pattern visualizer
Insert into a Binary Search Tree
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. 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..
Descend by comparison until a null child, then attach a new leaf there
time O(h) — O(log n) balanced, O(n) skewedspace O(h) recursion stack (O(1) with the iterative version)step 1 / 10
1
2
3
4
7
Call stack
insert(4, 5)
line 1
Enter node 4. Compare 5 against it to pick a side.
Pseudocode
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