Insert into a Binary Search Tree

Given the root of a binary search tree and a value val to insert, insert it and return the root of the (still valid) BST. The value is guaranteed not to already exist. Any valid BST resulting from the insertion is accepted, but a natural insert always creates a new leaf.

The tree is given/returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Insertion is search that doesn't stop early.

Walk down as if searching for val; you'll reach a null child.

That null slot is exactly where val belongs — attach a new leaf.

Common doubts

Following the comparisons keeps the ordering; the null pointer you reach is the only place val fits without violating the invariant.

No — a plain BST insert only adds a new leaf; rebalancing is a separate concern (AVL/red-black).

The new value becomes the root.

Interview follow-ups

· What an interviewer asks next.

Insert the leaf the same way, then rotate on the way back up to restore the height invariant (AVL) or color rules (red-black).

Find it, then handle 0/1/2 children — replacing a two-child node with its inorder successor.

Fun facts

The sequence of BST inserts determines the tree's shape — the same values in a different order give a different (possibly skewed) tree.
Inserting sorted values one by one produces a completely degenerate (linked-list) BST.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [4, 2, 7, 1, 3], val = 5
Output: [4, 2, 7, 1, 3, 5]
5 is inserted as the left child of 7.

Example 2

Input: root = [], val = 5
Output: [5]
Into an empty tree, the value becomes the root.

Constraints

- The number of nodes is in the range [0, 10^4] - -10^8 <= Node.val <= 10^8 - root is a valid BST - val does not exist in the original BST

Inserting into a BST is just search that doesn't stop early. Walk down as if looking for val; because it isn't present, you eventually fall off the tree — and that empty spot is exactly where val belongs (the invariant is preserved automatically). Attach a new leaf there. O(height).

Prerequisites

Before you start

· Concepts used directly in the solution.

BST invariant. Left < node < right, everywhere.

Search descent. Compare and go left/right.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Where does the new value go?”

At the empty slot where a search for it would end — as a new leaf.

“Can the tree be empty?”

Yes — then the new node is the root.

The ideal opening — say it like this

I search for the value; since it isn't there, the search runs off the tree, and that null slot is where it belongs.

I create a leaf there, which keeps the BST valid without any restructuring.

Understand the problem

Worked example — BST [4, 2, 7, 1, 3], val = 5

4  -> 5 > 4, go right
7  -> 5 < 7, go left -> null -> insert 5 as 7's left child
        4
       / \
      2   7
     / \  /
    1  3 5

Key observations

1Aha

Insertion point = where search ends

Searching for a value that isn't present lands exactly at the null slot where it belongs.

2Aha

Always a new leaf

A natural insert attaches a leaf; no existing nodes move.

3Aha

O(height)

It's one root-to-leaf descent.

Brute force vs optimal

	Recursive insert	Iterative insert
Idea	Recurse to the null child, return a new node	Loop to the null slot, attach a leaf
Time	O(height)	O(height)
Space	O(height)	O(1)

Both attach the same leaf; the iterative version uses O(1) space. Full code is in the Approaches selector below.

Summary

Key takeaway

Insert = search until you fall off the tree, then attach a new leaf at that null slot. The ordering is preserved automatically. O(height) time.

descend comparing val to node
at the first null child, attach new node(val)