Insert into a Binary Search Tree
Medium
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
For example, consider the following BST:
4
/ \
2 7
/ \
1 3
If we want to insert the value 5, the resulting BST could look like this:
4
/ \
2 7
/ \ /
1 3 5
Or like this:
4
/ \
2 7
/ \ \
1 3 5
Write a function that takes the root of a BST and a value to insert, and returns the root of the modified BST after the insertion. The function must maintain the BST property after the insertion.
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- It's guaranteed that
valdoes not exist in the original BST.
Solution
Naive Solution: Recursive Traversal
A simple, but not necessarily the most efficient, way to insert a value into a BST is to recursively traverse the tree until we find the appropriate place to insert the new node. At each node, we check if the value to insert is less than or greater than the current node's value. If it's less, we move to the left subtree; otherwise, we move to the right subtree. When we reach a null node (an empty spot), we create a new node with the given value and insert it there.
Code (Java)
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
Time Complexity
- O(h), where h is the height of the tree. In the worst case (skewed tree), h can be n, where n is the number of nodes. In the average case (balanced tree), h is log(n).
Space Complexity
- O(h) due to the recursive call stack. In the worst case, this can be O(n), and in the average case, O(log n).
Optimal Solution: Iterative Approach
An iterative approach avoids the overhead of the recursive call stack and can be slightly more efficient in practice. The logic remains the same: traverse the tree, comparing the value to insert with each node's value until an appropriate insertion point (a null node) is found.
Code (Java)
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
TreeNode current = root;
TreeNode parent = null;
while (current != null) {
parent = current;
if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
if (val < parent.val) {
parent.left = new TreeNode(val);
} else {
parent.right = new TreeNode(val);
}
return root;
}
}
Time Complexity
- O(h), where h is the height of the tree. Same as the recursive approach.
Space Complexity
- O(1) - Iterative solution has constant space complexity because it does not use recursion.
Edge Cases
- Empty Tree: If the root is
null, we simply create a new node with the given value and return it as the new root. Both the recursive and iterative solutions handle this case correctly. - Value Already Exists: The problem statement guarantees that the value to be inserted does not already exist in the BST, so we don't need to handle this case explicitly. If it was possible for the value to exist, we'd need to decide whether to insert a duplicate node (and where) or simply do nothing.
