Insert into a Binary Search Tree
Insert a new value into a binary search tree by walking down from the root to the empty child where it belongs and attaching it as a leaf.
Problem Understanding
Insert into a Binary Search Tree: given the root of a BST and a value that is not already in it, insert the value and return the root. Any valid BST is accepted.
Examples: [4,2,7,1,3], val 5 → [4,2,7,1,3,5]; [40,20,60,10,30,50,70], val 25 → 25 becomes the left child of 30.
The Intuition: Search Until You Fall Off
Search for the value as if it were already there. The search ends at an empty child, and that empty child is exactly where the value belongs.
- Smaller than the node: go left.
- Larger: go right.
- Empty child in that direction: attach the new node.
It is half of Delete Node in a BST, which runs the same search and then has to repair the tree. The result is still a BST, which Validate Binary Search Tree can confirm.
Interactive Walkthrough
INSERT 5 · OUTLINE = PATH WALKED
START AT ROOT
val
5
depth
0
Insert 5: walk down from the root 4 to the empty spot where it belongs
Next
5 > 4: go right to 7
BST
val
The node the walk is on is filled, the path behind it outlined, and the new leaf turns green. Try Empty tree for the base case.
Dry Run Table
Input: [40,20,60,10,30,50,70], val = 25.
| Node | Compare | Move |
|---|---|---|
| 40 | 25 < 40 | left to 20 |
| 20 | 25 > 20 | right to 30 |
| 30 | 25 < 30 | left is empty: attach |
Answer: [40,20,60,10,30,50,70,null,null,25].
The Solution Template
One walk down, one new link.
Insert into a Binary Search Tree Code
1var insertIntoBST = function(root, val) {2 if (!root) return new TreeNode(val);3 let node = root;4 while (true) {5 if (val < node.val) {6 if (!node.left) { node.left = new TreeNode(val); break; }7 node = node.left;8 } else {9 if (!node.right) { node.right = new TreeNode(val); break; }10 node = node.right;11 }12 }13 return root;14};
Edge Cases & Common Mistakes
- Empty tree: return the new node.
- Returning the new node instead of the root: the caller wants the original root back.
- Moving before checking: check that the child is empty before stepping into it, or the walk falls off with nowhere to attach.
- Duplicates: the problem guarantees the value is new; with duplicates allowed, pick one side consistently.
- Skewed trees: h can be n, so the worst case is O(n).
Summary
Walk down comparing with each node until the child in the chosen direction is empty, then attach the new node there and return the root. O(h) time, O(1) space iteratively.
More practice: DSA interview questions with answers · patterns cheat sheet