Insert into a Binary Search Tree: Walk the Path, Graft a Leaf
Insert into a Binary Search Tree in O(h) — walk the BST search path to the first empty slot and graft a new leaf, with JavaScript code and a full walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most tree problems tempt you into rebalancing, rotating, or rebuilding. Inserting into a Binary Search Tree needs none of that. A new value has exactly one legal home — the single empty child slot you reach by following the tree's own ordering rules — and once you find it, you drop a leaf and you're done.
The whole trick is realizing that a BST insertion is just a BST search that keeps walking until it falls off the tree. The place where the search would have failed is precisely where the new node belongs.
That reframe turns a scary-looking tree mutation into a five-line function.
The problem
You're given the root of a Binary Search Tree and a val to insert. Return the root of the tree after inserting the value. The input value is guaranteed not to already exist, and any valid BST that contains the new value is accepted as a correct answer.
Recall the BST invariant: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.
Insert val = 5 into:
4
/ \
2 7
/ \
1 3
Result:
4
/ \
2 7
/ \ /
1 3 5 // 5 slots in as the left child of 7Why does 5 land under 7? Start at the root 4: since 5 > 4, it must live in the right subtree. Move to 7: since 5 < 7, it must live in 7's left subtree. That subtree is empty, so 5 becomes 7's left child. Every comparison narrows the legal region until only one empty slot remains.
The brute force baseline
If you forget that a BST is ordered, the mechanical approach is to flatten it, add the value, and rebuild from scratch.
function insertIntoBST(root, val) {
// Inorder traversal yields every value in sorted order
const values = [];
(function inorder(node) {
if (!node) return;
inorder(node.left);
values.push(node.val);
inorder(node.right);
})(root);
values.push(val);
values.sort((a, b) => a - b);
// Rebuild a balanced BST from the sorted array
function build(lo, hi) {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
const node = new TreeNode(values[mid]);
node.left = build(lo, mid - 1);
node.right = build(mid + 1, hi);
return node;
}
return build(0, values.length - 1);
}This returns a valid BST, so it technically passes. But it touches every node twice — once to read, once to rebuild — for O(n) time and O(n) extra space, and it throws away the entire existing structure to change one thing. Inserting a single value should not require rebuilding the universe.
The key insight
The BST invariant already encodes where each value must go. At any node, comparing val against node.val eliminates an entire subtree from consideration: bigger means "go right," smaller means "go left." You never need to look at the side you didn't pick.
So you don't search for a spot — you're guided to it. This is the directed BST insertion pattern: follow the search path exactly as Search in a BST would, and instead of returning "not found" when you hit a null child, plant the new node there. Because you always run off the tree at an empty leaf slot, the inserted node is always a leaf. No existing pointers move, nothing rebalances.
The recursion expresses this beautifully: each call handles one node, delegates to exactly one child, and rewires that child pointer with whatever comes back.
The optimal solution
var insertIntoBST = function(root, val) {
if (!root) return new TreeNode(val);
if (root.val < val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}
return root;
};Read it as three claims:
if (!root) return new TreeNode(val)— the base case. Reachingnullmeans the walk found the unique empty slot, so build the leaf and hand it back up.if (root.val < val)— the current value is smaller than what we're inserting, sovalbelongs somewhere to the right. Recurse right and re-attach whatever the recursion returns toroot.right.else— otherwise recurse left and re-attach toroot.left.
The return root at the end is the part people forget. Every frame returns its own node unchanged, so the parent call can reassign the correct child pointer. Only the deepest call — the null one — returns something new. On the way back up, each root.right = ... or root.left = ... re-attaches the same subtree it descended into, except for the one edge that now points at the fresh leaf. The tree effectively rebuilds its spine, but every pointer except one lands right back where it started.
Walkthrough
Tracing insertIntoBST([4,2,7,1,3], 5). The call stack grows down the search path, then unwinds returning each node back to its parent.
| Step | Call | root.val | root.val < val? | Action |
|---|---|---|---|---|
| 1 | insertIntoBST(4, 5) | 4 | 4 < 5 is true | recurse right: root.right = insert(7, 5) |
| 2 | insertIntoBST(7, 5) | 7 | 7 < 5 is false | else branch → recurse left: root.left = insert(null, 5) |
| 3 | insertIntoBST(null, 5) | — | base case | return new TreeNode(5) |
| 4 | unwind to step 2 | 7 | — | 7.left now points at the new node; return 7 |
| 5 | unwind to step 1 | 4 | — | 4.right still points at 7; return 4 (final root) |
Two comparisons decided everything. At step 1, 5 > 4 pushed us right; at step 2, 5 < 7 pushed us into 7's empty left slot. Step 3 is the only call that allocates. Steps 4 and 5 re-attach unchanged pointers — 7.left is the sole edge that actually changed — and return the root back to the caller.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Flatten + rebuild | O(n) | O(n) | reads and reconstructs every node to change one |
| Directed insertion (recursive) | O(h) | O(h) | one comparison per level down a single path; stack depth = height |
| Directed insertion (iterative) | O(h) | O(1) | same walk with a loop, no call stack |
h is the height of the tree. For a balanced BST that's O(log n); for a fully skewed (linked-list-shaped) BST it degrades to O(n). The recursive version's space is the call stack — one frame per level of descent. Swap the recursion for a while loop and you drop the extra space to O(1), which is the iterative variant shown in many editorial solutions.
Common mistakes
- Returning the new node instead of the root. The function must return the original root so the caller's child pointer stays intact. Returning the freshly created leaf orphans the rest of the tree.
- Forgetting the empty-tree case. If
rootisnullon the very first call, the base case correctly returns the new node as the standalone root. Skip that check and you'll crash onroot.val. - Using
<=on the wrong side. This solution sends equal values left via theelsebranch, but the problem guaranteesvalisn't already present, so the tie case never fires — don't add special handling for duplicates. - Rebalancing after insertion. A plain BST insert never rotates. The new node is always a leaf; the shape only changes by one edge. Rebalancing logic belongs to AVL or Red-Black trees, not this problem.
Where this pattern shows up next
Directed BST traversal — comparing against the current node to discard half the tree — is the backbone of every BST operation:
- Search in a Binary Search Tree — the exact same walk, except it stops at the match instead of running off the end.
- Validate Binary Search Tree — verifies the ordering invariant that makes this insertion path unique in the first place.
- Lowest Common Ancestor of a Binary Search Tree — uses the same "go left or right by comparison" logic to find where two search paths diverge.
- Kth Smallest Element in a BST — leans on inorder traversal, the ordering guarantee's other big payoff.
You can also step through the insertion interactively to watch the call stack grow down the search path and the new leaf pop into its slot.
FAQ
Why is a new node always inserted as a leaf?
Because the search path only stops when it reaches an empty child slot. As long as a child exists, the comparison tells you to keep descending into it. You only stop at null, which is by definition a spot with no children below it — so the node you create there has no subtrees and is a leaf. This is why plain BST insertion never needs to move existing pointers or rebalance.
What is the time complexity of inserting into a BST?
O(h), where h is the height of the tree. Each level of descent does one constant-time comparison, and you descend at most h levels before hitting an empty slot. For a balanced tree that's O(log n); for a degenerate, fully-skewed tree it's O(n). The recursive solution also uses O(h) space for the call stack, which an iterative version reduces to O(1).
Do I need to return the root from the insert function?
Yes, and it's the single most common bug. Each recursive call returns its own node so the parent can re-attach it via root.left = ... or root.right = .... The base case returns the newly created node, and that return value is what wires the new leaf onto its parent. Return the wrong thing — like the new node from a deep call — and every ancestor loses its connection to the rest of the tree.
Does this handle inserting into an empty tree?
It does, with no special code. When the tree is empty, root is null on the first call, the if (!root) base case fires immediately, and the function returns a single new node that becomes the whole tree's root. That same base case does double duty: it's both the "empty tree" case and the "found the empty slot" case at the bottom of every search path.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.