Insert into a BST
MediumWalk down, hang a new leaf
Walk down — left for smaller, right for bigger — until you find an empty spot to hang the new value.
The idea
Follow the ordering down the tree until you reach an empty spot, then attach the new node there as a leaf. No rotations needed for a plain BST.
Step 1 of 5. Insert 6. Walk down the ordering until we reach an empty spot.
1/5
Optimal
timeO(h)spaceO(1)
Find the empty slot.
1function insert(root, key) {2 if (!root) return new Node(key);3 let cur = root;4 while (true) {5 if (key < cur.val) {6 if (!cur.left) { cur.left = new Node(key); break; }7 cur = cur.left;8 } else {9 if (!cur.right) { cur.right = new Node(key); break; }10 cur = cur.right;11 }12 }13 return root;14}Input
- nodes
- 7, 6 edges
Output
- inserted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- bst = [4,2,7,1,3], insert = 5
- Output:
- [[4], [2, 7], [1, 3, 5]]
- Explanation:
- 5 slots in as the left child of 7.
Example 2
- Input:
- bst = [8], insert = 3
- Output:
- [[8], [3]]
- Explanation:
- 3 becomes the left child of 8.
Example 3
- Input:
- bst = [5,3,8], insert = 9
- Output:
- [[5], [3, 8], [9]]
- Explanation:
- 9 hangs off 8 on the right.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.