On this page

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, and val is not already present.

Intuition

1 8
2 / \
3 4 12
4 / \ / \
5 2 6 10 14

Inserting 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

  1. If the tree is empty, return a new node.
  2. Start cur at the root and loop:
    • If val < cur.val: if cur.left exists, move to it. Otherwise attach the new node as cur.left and stop.
    • Else: if cur.right exists, move to it. Otherwise attach the new node as cur.right and stop.
  3. 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