Insert a given node in BST
MediumDescend to the empty spot and attach
Problem
Insert a value into a BST so the BST property is preserved, and return the root.
Walk down comparing values until you fall off the tree, then hang the new node there.
The idea
Follow the same comparisons as a search until you fall off the tree, and attach the new node there. Inserting only at a leaf position is what preserves the ordering without any restructuring.
The trick
- No rotations needed for a plain BST.
- Duplicates need a policy — reject them, or always send them one way.
- O(height).
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.