Insert into a Binary Search Tree

The problem. Given the root of a binary search tree and a value val that is not already in the tree, insert it and return the root of the resulting BST. Any valid BST is accepted, but the standard answer — and the one interviewers expect — adds the value as a new leaf.

Inserting 5 into the tree 4, 2, 7, 1, 3. 5 is greater than 4 so go right to 7; 5 is less than 7 and 7 has no left child, so 5 becomes the left child of 7. No other node moves.

Example

root = [4, 2, 7, 1, 3], val = 5                  ->  [4, 2, 7, 1, 3, 5]
root = [40, 20, 60, 10, 30, 50, 70], val = 25    ->  [40, 20, 60, 10, 30, 50, 70, null, null, 25]
root = [], val = 5                               ->  [5]

The idea

Search for val as if it were there. The search ends by stepping off the tree at an empty child — and that empty child is exactly where val belongs: every comparison on the way agreed it fits there. Attaching a leaf never disturbs the rest of the tree.

1. Recursion: return the new subtree root

Each call returns the root of its subtree after the insert. For an empty subtree that's the new node; otherwise it's the same node, with one child replaced by the result of the recursive call. This "return the subtree and re-attach it" shape comes back in delete, trim and many other BST problems.

Dry-run simulator

Insert into a BST (recursion re-attaches each child)

The new node is created where the walk runs out; each call re-attaches its child on the way back.

1function insertIntoBST(root, val) {2  if (root === null) return new TreeNode(val);             // the empty spot: the new leaf3  if (val < root.val) root.left = insertIntoBST(root.left, val);4  else root.right = insertIntoBST(root.right, val);5  return root;                                             // this subtree's root is unchanged6}

JavaScript6 lines

Time O(h), space O(h) for the call stack.

2. A loop that remembers the parent

1function insertIntoBST(root, val) {2  const fresh = new TreeNode(val);3  if (root === null) return fresh;4  let node = root;5  for (;;) {6    const side = val < node.val ? "left" : "right";7    if (node[side] === null) {8      node[side] = fresh;                                  // attach to the empty side9      return root;10    }11    node = node[side];12  }13}

JavaScript13 lines

Time O(h), space O(1). Same path, no call stack.

Comparing the approaches

Recursion: O(h) time, O(h) space. Loop: O(h) time, O(1) space.

Edge cases to test

Empty tree — the new node is the root.
New smallest or largest value — it goes at the far left or far right.
A chain — inserting at the end walks the whole chain: O(n).
Returning the root — forgetting to return it (or returning the new node) is the classic bug.

Variations

Insert at the root — insert as a leaf, then rotate it up; recently inserted values become fastest to find.
Insert into a self-balancing tree — insert as a leaf, then fix the balance on the way back up with rotations.
Insert with duplicates — decide where equal values go (or keep a count per node).

Prev Next

Was this helpful?