Insert Into a Binary Search Tree
You are given the root of a BST and a val to insert. Insert it so the tree remains a valid BST and return the root. The value is guaranteed not to exist in the tree, and any valid result is accepted.
Constraints:
- The number of nodes is in the range
[0, 10^4]. -10^8 <= Node.val <= 10^8, all values are unique, andvalis not already present.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14Inserting 5: at 8 go left, at 4 go right, at 6 go left, and 6 has no left child. That empty spot is where 5 belongs. The new node always becomes a leaf, so no existing node has to move.
In other words, insertion is a search that fails, followed by attaching the new node where the search fell off the tree.
Approach: Search, Then Attach at the Empty Spot
- If the tree is empty, return a new node.
- Start
curat the root and loop:- If
val < cur.val: ifcur.leftexists, move to it. Otherwise attach the new node ascur.leftand stop. - Else: if
cur.rightexists, move to it. Otherwise attach the new node ascur.rightand stop.
- If
- Return the original root.
Only one if decides left or right at each step, and the insertion happens when the next child is missing.
Code
class Solution {public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) return new TreeNode(val);TreeNode* cur = root;while (true) {if (val < cur->val) {if (cur->left != nullptr) {cur = cur->left;} else {cur->left = new TreeNode(val);break;}} else {if (cur->right != nullptr) {cur = cur->right;} else {cur->right = new TreeNode(val);break;}}}return root;}};
Complexity
Time: O(h)
We walk one root-to-leaf path: O(log n) balanced, O(n) skewed.
Space: O(1)
The iterative version uses no extra memory beyond the new node.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"Insertion in a BST is a search that fails. I start at the root and compare the value with the current node. If it is smaller I go left, otherwise I go right. The moment the child I need is missing, I attach the new node there, and it becomes a leaf, so no existing node moves and the BST property is preserved. I return the original root, and if the tree was empty I just return the new node. Time is O of h and space is O of one."
Next TopicDelete Node in a Bst