Community Problem
Insert into a Binary Search Tree
Difficulty: Medium
Insert a new value into a BST while preserving the ordering invariant; any valid resulting BST is accepted.
Insert into a Binary Search Tree
Insert a new value into a BST while preserving the ordering invariant; any valid resulting BST is accepted.
By @davidmorgan
January 24, 2026
·
Updated May 18, 2026
624 views
16
4.2 (11)
I had to write this exact function from scratch when I was building a small ordered set for a CLI parser, and the recursion is so clean it doubles as a teaching moment for anyone who has only ever read about BSTs. The catalog covers Validate BST and Kth Smallest, but it skipped the constructive side: how do you actually grow a BST one node at a time?
Insert into a Binary Search Tree
Given the root of a binary search tree (BST) and an integer val to insert into the tree, return the root of the BST after the insertion. It is guaranteed that val does NOT already exist in the original BST.
Notice that there may exist multiple valid BSTs after the insertion. You may return any of them, as long as the resulting tree is a valid BST.
Examples
Example 1:
- Input:
root = [4, 2, 7, 1, 3],val = 5 - Output:
[4, 2, 7, 1, 3, 5] - Explanation:
5 > 4so go right.5 < 7so go left. The left child of7is empty, so5becomes the left child.
Example 2:
- Input:
root = [40, 20, 60, 10, 30, 50, 70],val = 25 - Output:
[40, 20, 60, 10, 30, 50, 70, null, null, 25] - Explanation:
25 < 40,25 > 20,25 < 30. The left child of30is empty, so25becomes the left child.
Example 3:
- Input:
root = [],val = 5 - Output:
[5] - Explanation: An empty tree gets a single root node.
Example 4:
- Input:
root = [4, 2, 7, 1, 3],val = 6 - Output:
[4, 2, 7, 1, 3, 6] - Explanation:
6 > 4,6 < 7. Insert as left child of7.
Constraints
- The number of nodes in the tree will be in the range
[0, 10^4]. -10^8 <= Node.val <= 10^8.- All the values
Node.valare unique. -10^8 <= val <= 10^8.valdoes not exist in the original BST.
Follow-up
Can you do it iteratively? When does the iterative version pay off (hint: stack frames matter for very tall trees)?
Solution
Hints
Solution Walkthrough
Approach: Iterative BST Walk to the First Null Slot (O(h) time, O(1) space)
BST insertion has the cleanest correctness proof in all of CS: walk left when smaller, walk right when bigger, drop the new node into the first null pointer you find. The result automatically preserves the BST invariant for everyone above and below.
Algorithm
- If
rootisnull, return a newTreeNode(val)(the tree was empty). - Set
cur = root. - Loop:
- If
val < cur.val: ifcur.leftisnull, attach a new node ascur.leftand returnroot. Elsecur = cur.left. - Else: symmetric on the right.
Why It Works
At the moment we attach the new node, every ancestor's invariant still holds: when we descended left from parent, every node on that side (now including the new one) is < parent.val. The mirror is true for right descents. Because the new node has no children, its own subtree is trivially a BST (a single node).
Complexity
Sample BST and insertion of 5
4
/ \
2 7
/ \
1 3
Insert 5
4
/ \
2 7
/ \ /
1 3 5Metric Value
Time O(h) where h is the BST height
Space O(1) iterative; O(h) recursive (call stack)Pitfalls
- Iterative loop without an exit. A bug-prone variant uses
while (cur !== null)and tries to attach inside the loop. The cleaner version useswhile (true)and returns from inside the branch where the child is null. - Forgetting the empty-tree case. If
rootisnull, the loop never starts and a fresh node should be returned directly. - Equal values. The problem guarantees
valis unique, but a robust insert needs a convention for duplicates: either reject, or treat==as "go right" (which is what the algorithm does here when written withif (val < cur.val) ... else ...).
Solution Code