Insert into a Binary Search Tree — Problem & Solution
Insert into a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Insert into a Binary Search Tree is a medium coding problem on binary search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Binary Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree and an integer value that is not yet in the tree. Insert value and return the root of the tree.
More than one valid search tree can result, so insert it this way: search for value from the root as usual (left when it is smaller than a node, right when it is larger), and place a new node holding value at the empty spot where the search falls off the tree. Nothing else moves.
Example 1
Input: root = [4,2,7,1,3], value = 5
Output: [4,2,7,1,3,5]
Explanation: 5 > 4 goes right to 7, then 5 < 7 goes left — an empty spot, so 5 becomes 7's left child.
Example 2
Input: root = [40,20,60,10,30,50,70], value = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Explanation: The search goes 40 → 20 → 30 and falls off to the left of 30.
Example 3
Input: root = [], value = 5
Output: [5]
Explanation: Inserting into an empty tree makes the new node the root.
Constraints
The number of nodes in the tree is in the range [0, 10^4]-10^8 <= Node.val <= 10^8All the values Node.val are unique-10^8 <= value <= 10^8value does not exist in the original BST
Hints for Insert into a Binary Search Tree
Hint 1
Where would a search for
valueend? At a node whose child on the sidevaluepoints to is missing.Hint 2
That missing child is exactly where the new node goes; the tree stays a valid search tree.
Hint 3
Walk down iteratively and keep the current node, or recurse and return the subtree's root so the parent can reattach it. Don't forget the empty tree.
How to solve Insert into a Binary Search Tree
A search for a missing value ends at an empty child pointer, and that position is consistent with every ancestor's ordering. Hanging the new node there is the simplest valid insertion and leaves the rest of the tree untouched.
Approach
- If
rootis null, return a new node holdingvalue. - Start at
cur = root. Ifvalue < cur.val, look atcur.left; otherwise atcur.right. - If that child is null, attach the new node there and stop; otherwise move to it and repeat.
- Return
root.
Why it works
At each step value goes to the side the search-tree property requires relative to the current node, so on the final path every ancestor sees it on its correct side. Attaching a leaf changes no other link, so all other order relations still hold.
Complexity
- Time —
O(h), the tree's height — O(log n) when balanced, O(n) for a chain - Space —
O(1) iteratively (O(h) recursively)
Pitfalls
- The empty tree: the new node is the root.
- Do not try to rebalance or insert higher up — the statement fixes the insertion as a new leaf.
Reference solution
Python
from typing import Optional
def insertIntoBST(root: Optional[TreeNode], value: int) -> Optional[TreeNode]:
node = TreeNode(value)
if root is None:
return node
cur = root
while True:
if value < cur.val:
if cur.left is None:
cur.left = node
break
cur = cur.left
else:
if cur.right is None:
cur.right = node
break
cur = cur.right
return rootJava
public static TreeNode insertIntoBST(TreeNode root, int value) {
TreeNode node = new TreeNode(value);
if (root == null) return node;
TreeNode cur = root;
while (true) {
if (value < cur.val) {
if (cur.left == null) { cur.left = node; break; }
cur = cur.left;
} else {
if (cur.right == null) { cur.right = node; break; }
cur = cur.right;
}
}
return root;
}C++
TreeNode* insertIntoBST(TreeNode* root, int value) {
TreeNode* node = new TreeNode(value);
if (!root) return node;
TreeNode* cur = root;
while (true) {
if (value < cur->val) {
if (!cur->left) { cur->left = node; break; }
cur = cur->left;
} else {
if (!cur->right) { cur->right = node; break; }
cur = cur->right;
}
}
return root;
}JavaScript
var insertIntoBST = function(root, value) {
var node = new TreeNode(value);
if (root === null) return node;
var cur = root;
while (true) {
if (value < cur.val) {
if (cur.left === null) { cur.left = node; break; }
cur = cur.left;
} else {
if (cur.right === null) { cur.right = node; break; }
cur = cur.right;
}
}
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search · Binary Trees and Tree Traversals