#701
Insert into a Binary Search Tree
Medium BST walk to a null slot
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Insert a new value (not already present) into a BST and return the root.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add a new value in the right place.
Why this works: walk down as if searching; the empty spot where you fall off is where the new node goes.
Example: insert 5 into 4 (2, 7)
5 > 4 → right 7, 5 < 7 → left is empty → place 5✦Hints open one at a time
Walk down as if searching; the empty spot where the search ends is where the new node goes.
Recursion makes the re-linking simple: root.left = insert(root.left, val).
↗Approach
If root is null, return a new node. Otherwise recurse into the correct side and assign the result back.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } // provided by LeetCode
*/
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;
}
}!Common mistake
Forgetting to return a new node for an empty tree.
Complexity
- Time: O(h).
- Space: O(h) recursion.
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon