Insert into a Binary Search Tree
Insert into a Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern.
The best approach, iterative, runs in O(h) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive up.
Problem
Insert val into a binary search tree so that it stays a valid BST, and return the root. The value is guaranteed not to exist in the tree yet.
Examples
Example 1
- Input
root = [4, 2, 7, 1, 3], val = 5- Output
[4, 2, 7, 1, 3, 5]- Why
- 5 becomes the left child of 7.
Example 2
- Input
root = [], val = 8- Output
[8]
Constraints
- The tree has
0to10^4nodes; val is not already in the tree. - Any valid BST result is accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive | O(h) | O(h) |
| Iterative | O(h) | O(1) |
1Recursive
O(h)O(h)Go left or right like a search. When you reach null, return a new node, and the parent attaches it.
- if root == null return new TreeNode(val).
- Recurse into the correct side and assign the result to that child.
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;
}
}class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return rootclass Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val < root->val) root->left = insertIntoBST(root->left, val);
else root->right = insertIntoBST(root->right, val);
return root;
}
};function insertIntoBST(root, 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;
}2Iterative
O(h)O(1)Walk down to the parent whose child spot is empty in the right direction and attach the new node there.
- If root is null, return a new node.
- Loop: pick the side; if that child is null, attach and return root; otherwise move there.
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode node = new TreeNode(val);
if (root == null) return node;
TreeNode cur = root;
while (true) {
if (val < 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;
}
}class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
node = TreeNode(val)
if root is None:
return node
cur = root
while True:
if val < 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 rootclass Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* node = new TreeNode(val);
if (root == nullptr) return node;
TreeNode* cur = root;
while (true) {
if (val < cur->val) {
if (cur->left == nullptr) { cur->left = node; break; }
cur = cur->left;
} else {
if (cur->right == nullptr) { cur->right = node; break; }
cur = cur->right;
}
}
return root;
}
};function insertIntoBST(root, val) {
const node = new TreeNode(val);
if (root === null) return node;
let cur = root;
while (true) {
if (val < 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;
}Edge cases to test
- Empty tree
- Inserting a new minimum or maximum
Hints
Hint 1
Search for val as if it existed; the null spot where the search ends is where it goes.
FAQ
What is the best time complexity for Insert into a Binary Search Tree?
Iterative runs in O(h) time and O(1) extra space.
Which pattern does Insert into a Binary Search Tree use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Binary Search Tree Iterator.
Is there a brute force solution for Insert into a Binary Search Tree?
Yes. Recursive takes O(h) time and O(h) space. Go left or right like a search.
Which edge cases should I test for Insert into a Binary Search Tree?
Empty tree; Inserting a new minimum or maximum.