Insert into a Binary Search Tree
Problem Statement
Given the root of a BST and a value val that does not already exist in the tree, insert val into the BST and return the root of the updated tree. If the tree is empty, the inserted node becomes the root.
Input
A BST root and a new integer val to insert.
Output
The root of the BST after attaching a new node with value val in the correct position.
Constraints
- •
0 <= number of nodes <= 10^4 - •
-10^8 <= Node.val <= 10^8 - •
All existing node values are unique - •
-10^8 <= val <= 10^8 - •
val does not exist in the original BST
Examples
Example 1
root = **[4,2,7,1,3]**, val = **5**
**[4,2,7,1,3,5]**Example 2
root = **[40,20,60,10,30,50,70]**, val = **25**
**[40,20,60,10,30,50,70,null,null,25]**Example 3
root = **[]**, val = **5**
**[5]**Learning Objectives
- Find the only empty child position where the new value can be attached.
- Explain why insertion in a BST changes only one root-to-leaf path.
- Use recursive returns to reconnect the possibly new subtree root.
- Compare recursive insertion with the iterative constant-space version.
Intuition
Pattern Recognition
The signal is adding one value to an existing BST. Because the value does not already exist, the final node must be a new leaf. The BST property tells you exactly which path to follow: smaller values go left, larger values go right.
The common trap is trying to rebuild or rebalance the whole tree. Plain BST insertion does neither. It walks down one branch until the child pointer that should contain val is empty, then attaches a new leaf. In recursive form, each call returns the root of its subtree so the parent link stays correct, including the empty-tree case where the new node is the returned root.
Common mistakes
- ×Forgetting to return **root** after recursive insertion, which disconnects the unchanged ancestors.
- ×Creating a new node but not assigning it to **root.left** or **root.right**.
- ×Ignoring the empty-tree case where the new node is the whole answer.
- ×Assuming insertion automatically balances the BST; this problem preserves shape except for one new leaf.
Algorithm Explanation
Key idea
Insertion is search plus attachment. Compare val with the current node. If val is smaller, insert into the left subtree. If larger, insert into the right subtree. When the recursive call reaches null, create and return a new node. Every parent stores the returned subtree root and returns itself upward.
Recursion walkthrough
Use [5,3,8,2,4,7,9] and insert 6. Start at 5. Since 6 > 5, recurse into the right subtree rooted at 8. Since 6 < 8, recurse into the left subtree rooted at 7. Since 6 < 7, recurse into 7.left, which is empty. Create a new node 6 and return it. The call at 7 stores that node as 7.left, then returns 7. The calls at 8 and 5 return their unchanged roots, preserving the full tree.
Algorithm
- If root is null, return a new node containing val.
- If val < root.val, set root.left to the result of inserting into root.left.
- If val > root.val, set root.right to the result of inserting into root.right.
- Return root so the caller keeps the correct subtree root.
- The original caller receives the possibly new overall root.
Solutions
Solution 1: Recursive subtree return
Use this when teaching or explaining BST mutation. The return value cleanly handles both normal child insertion and the empty-root case.
Treat insertion as a recursive operation that returns the root of the updated subtree. The first null position on the search path becomes the new leaf.
Step-by-step
- If the current subtree is null, create and return a new node.
- If val is smaller than root.val, recursively insert into the left subtree and store the returned root in root.left.
- If val is larger, recursively insert into the right subtree and store the returned root in root.right.
- Return root from every non-empty call.
- The top-level return is the root of the updated BST.
O(h)
O(h)
Only one search path is visited. The recursion stack is O(log n) for a balanced tree and O(n) for a skewed tree.
Java implementation
Solution 2: Iterative leaf attachment
Use this when the interviewer asks for O(1) auxiliary space or when you want to avoid recursion depth on a skewed tree.
Walk down the BST until the correct child pointer is empty. Attach the new node at that empty pointer and return the original root.
Step-by-step
- If root is null, return a new node.
- Keep current at the node being inspected.
- If val is smaller and current.left is empty, attach the new node there and stop.
- If val is smaller and current.left exists, move left.
- Mirror the same logic on the right when val is larger.
- Return the original root after attachment.
O(h)
O(1)
The loop follows one root-to-leaf path: O(log n) balanced, O(n) skewed.
Java implementation
Dry Run
Sample input
root = [5,3,8,2,4,7,9], val = 6. Follow the recursive calls until an empty child is found.
| step | current node | comparison | recursive direction | returned subtree root |
|---|---|---|---|---|
| 1 | 5 | 6 is greater than 5 | insert into right subtree | 5 after its right child is updated |
| 2 | 8 | 6 is less than 8 | insert into left subtree | 8 after its left child is updated |
| 3 | 7 | 6 is less than 7 | insert into left subtree | 7 after its left child is updated |
| 4 | null | empty spot found | create node 6 | new subtree root 6 |
The new node becomes 7.left. Every ancestor returns itself, so the final root remains 5 while the tree now includes 6.
Interview Tips
State that the inserted value becomes a leaf in a standard BST. Then choose recursive or iterative style based on what the interviewer values. The recursive return pattern is especially important: assigning root.left or root.right to the returned subtree root is what handles the empty child and preserves ancestors.
Likely follow-ups
- How would insertion change if duplicate values were allowed?
- How would you keep the tree balanced after insertion?
- Can you insert a batch of values to minimise final tree height?
- How would you implement insertion when each node also stores its subtree size?
Similar Problems
Key Takeaways
- BST insertion follows exactly one compare-and-branch path.
- The new value is attached at the first empty child where the search would continue.
- Recursive insertion returns the updated subtree root to reconnect parent pointers.
- Insertion does not rebalance the tree unless a separate balancing structure is used.