Loading…

easyTreesFrequently asked

Binary Search Tree: Insertion

Q: How do you solve Binary Search Tree: Insertion using the Recursive Insert — Return the Subtree Root (Optimal) approach?

When to use it: Start here. The 'return root and reassign' idiom is the cleanest and the most reusable. Insertion is binary search that terminates in a node creation. At each node you ask one question — is the new value smaller or larger? — and descend accordingly, until you run off the bottom of the tree into a null slot. That null slot is the *unique* place the value can sit without violating the ordering invariant. **The base case creates the node.** When the recursion reaches `root == null`, you've located the empty slot. Returning `new Node(v)` here is what actually creates the node; every level above just passes that return value back up. **The return-and-reassign idiom.** Each recursive call returns the (possibly updated) root of the subtree it was given. The parent writes that return value back into `root.left` or `root.right`. On the way down nothing changes except the one null link at the bottom, which now points to the new node. Writing `root.left = insert(root.left, v)` rather than just calling `insert(root.left, v)` is essential — without the assignment, the new node is created but never linked into the tree. **Why it's always a leaf.** Because we only stop at a null child, the new node has no children of its own at insert time — it's a leaf. A plain BST insert never restructures existing nodes. **Cost.** The work is proportional to the path length from root to the insertion point, i.e. the height h. Balanced trees give O(log n); a degenerate, sorted-input tree degrades to O(n), which motivates self-balancing variants. Time complexity: O(h). Space complexity: O(h).

Q: How do you solve Binary Search Tree: Insertion using the Iterative Insert — Track the Parent approach?

When to use it: Offer if recursion is discouraged or to show you can manage the parent link explicitly. The iterative version makes the descent explicit and uses no call stack, so its extra space is O(1). **Two pointers and a side.** Keep `cur` (the node you're examining) and `parent` (the node above it). At each step compare `v` with `cur.data`: if smaller, remember you went left and move `cur = cur.left`; otherwise remember right and move `cur = cur.right`. When `cur` becomes null you've found the empty slot, and `parent` is the node that should adopt the new leaf. **Attach on the recorded side.** You must remember whether the final step went left or right, because once `cur` is null you can't tell. With that boolean (or by re-comparing `v` against `parent.data`), set `parent.left` or `parent.right` to the new node. **The empty-tree special case.** If the tree starts empty, there's no parent to attach to — the new node is the root, so handle that before the loop. This is the one branch the recursive version folds neatly into its base case but the iterative version must spell out. **Same shape as the recursion.** Both follow one root-to-leaf path; the iterative form just replaces the implicit call-stack bookkeeping with an explicit parent pointer, trading O(h) stack space for O(1). Time complexity: O(h). Space complexity: O(1).

Trees & BST · 31 of 41 · 7 min

Given the root of a binary search tree and a value v, insert v into the BST and return the root of the updated tree.

A binary search tree keeps, for every node, all smaller values in its left subtree and all larger values in its right subtree. You may assume v is not already present.

In plain English

Find the unique position where the new value preserves the BST invariant — that position is always an empty (null) child slot reached by comparing the value against nodes on the way down. Create the node there and return the (possibly new) root so the caller's reference stays correct.

Examples

Example 1

Input: BST = [4,2,7,1,3], insert 6
Output: 6 becomes the left child of 7
Note: 6 > 4 → go right to 7. 6 < 7 → go left; 7's left is null → insert 6 there.

Example 2

Input: BST = [], insert 5
Output: 5 becomes the root
Note: Empty tree — the new node is the root (base case).

Example 3

Input: BST = [4,2,7,1,3], insert 0
Output: 0 becomes the left child of 1
Note: 0 < 4 → left to 2; 0 < 2 → left to 1; 0 < 1 → left null → insert.

Constraints

0 ≤ number of nodes ≤ 500 (the tree may be empty)
1 ≤ node value ≤ 500
The value to insert is not already in the tree
The BST ordering invariant holds before insertion

Clarifying questions4First question: Can the tree be empty?Explore questions

Q1.Can the tree be empty?
Yes. If root is null, the inserted node becomes the new root — that's the recursion's base case.
Q2.Can the value already exist?
The problem says values are unique. If duplicates were allowed, you'd decide a consistent side (usually right) or store a count instead of a new node.
Q3.Does the tree need to stay balanced?
No — a plain BST insert doesn't rebalance. The new node is hung at a leaf, so worst-case height can degrade to O(n). Self-balancing trees solve that separately.
Q4.Where does the new node end up?
Always as a leaf — the first null child slot the comparisons lead you to.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Walk down the BST comparing the new value with each node: go left if it's smaller, right if it's larger. When you fall off the tree (hit a null child), that empty spot is exactly where the value belongs — create the node there. Recursively, return a new node when root is null, else recurse into the correct side and return root. It's O(h) time — O(log n) for a balanced tree, O(n) for a skewed one — and the new node is always inserted as a leaf.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand the BST ordering invariant and can descend by comparison to the correct null slot, returning the reattached subtree.

Where candidates slip

Forgetting to return/reassign the subtree root (so the new node is created but never linked), or inserting at the root instead of at a leaf.

How to stand out

State that a plain BST insert always creates a leaf, give both the clean recursive form and an iterative parent-tracking version, and note the O(h) cost and why balancing matters under skew.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Insert — Return the Subtree Root (Optimal)Optimal	`O(h)`	`O(h)`	Start here. The 'return root and reassign' idiom is the cleanest and the most reusable.	Read
2	Iterative Insert — Track the Parent	`O(h)`	`O(1)`	Offer if recursion is discouraged or to show you can manage the parent link explicitly.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAt node, value vroot == null?YesNoExplore the full tree

Descent decision at each node

How to read it:Compare v with the current node, branch, and stop at the first null child.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive Insert — Return the Subtree Root (Optimal)

TimeO(h)SpaceO(h)

Start here. The 'return root and reassign' idiom is the cleanest and the most reusable.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where can a new value go so the BST invariant still holds? Compare it against the root: which subtree must it live in?

2Hint 2Explore hint

Recurse into the correct subtree. What does it mean when that subtree is null — where exactly does the value belong?

3Hint 3Explore hint

Base case: a null subtree means you've found the empty slot — return a new node. Otherwise recurse, reassign the child link, and return the current root.

A · Core idea

Insertion is binary search that terminates in a node creation. At each node you ask one question — is the new value smaller or larger? — and descend accordingly, until you run off the bottom of the tree into a null slot. That null slot is the unique place the value can sit without violating the ordering invariant.

The base case creates the node. When the recursion reaches root == null, you've located the empty slot. Returning new Node(v) here is what actually creates the node; every level above just passes that return value back up.

The return-and-reassign idiom. Each recursive call returns the (possibly updated) root of the subtree it was given. The parent writes that return value back into root.left or root.right. On the way down nothing changes except the one null link at the bottom, which now points to the new node. Writing root.left = insert(root.left, v) rather than just calling insert(root.left, v) is essential — without the assignment, the new node is created but never linked into the tree.

Why it's always a leaf. Because we only stop at a null child, the new node has no children of its own at insert time — it's a leaf. A plain BST insert never restructures existing nodes.

Cost. The work is proportional to the path length from root to the insertion point, i.e. the height h. Balanced trees give O(log n); a degenerate, sorted-input tree degrades to O(n), which motivates self-balancing variants.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

BST = [4,2,7,1,3], insert 6

Inserting 6 into [4,2,7,1,3]

How to read it:Path 4 → 7 → (left null); 6 becomes 7's left child.

Rendering diagram…

Final result6 is the left child of 7

C · Code with teaching comments

solution.javaJava

Recursive Insert — Return the Subtree Root (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public Node insert(Node root, int v) {
10
    if (root == null) return new Node(v);   // empty slot found → create
11
    if (v < root.data) {
12
        root.left = insert(root.left, v);   // reassign the left link
13
    } else {
14
        root.right = insert(root.right, v); // reassign the right link
15
    }
16
    return root;                            // hand this subtree back up
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(h) timeO(h) spaceOpen the invariant and proofExplore the proof

The 'recurse, reassign the child link, return the subtree root' pattern handles insert, delete, and many tree rewrites uniformly. The assignment is the part beginners drop — say it out loud: 'the child link gets rebound to whatever the recursion returns.'

ComplexityO(h) time, O(h) space — You follow a single root-to-leaf path, doing O(1) comparison per level → O(h) time. The recursion stack is also O(h). For a balanced tree h ≈ log n; for a skewed tree h = n.

E · Edge cases and pitfalls6BST = [], insert 5 — root is null → return Node(5); it becomes the root.Explore edge cases

Edge cases handled

BST = [], insert 5root is null → return Node(5); it becomes the root.
Insert a value smaller than all nodesDescends fully left, attaches as the leftmost leaf.
Insert into a left-skewed chainPath length is O(n) — worst-case insertion cost.

Pitfalls

Calling insert(root.left, v) without assigning the result — node created but never linked.
Inserting at the root or an interior node instead of at the null leaf slot.
Mishandling duplicates when the problem allows them — pick a consistent side or a count.

03.2

Approach 2 of 2

Iterative Insert — Track the Parent

TimeO(h)SpaceO(1)

Offer if recursion is discouraged or to show you can manage the parent link explicitly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk down with two pointers: the current node and its parent. When current becomes null, the parent is where you attach.

2Hint 2Explore hint

Remember which side you descended (left or right) so you attach the new node on the correct side of the parent.

3Hint 3Explore hint

Handle the empty-tree case separately: if root is null, the new node is simply the root.

A · Core idea

The iterative version makes the descent explicit and uses no call stack, so its extra space is O(1).

Two pointers and a side. Keep cur (the node you're examining) and parent (the node above it). At each step compare v with cur.data: if smaller, remember you went left and move cur = cur.left; otherwise remember right and move cur = cur.right. When cur becomes null you've found the empty slot, and parent is the node that should adopt the new leaf.

Attach on the recorded side. You must remember whether the final step went left or right, because once cur is null you can't tell. With that boolean (or by re-comparing v against parent.data), set parent.left or parent.right to the new node.

The empty-tree special case. If the tree starts empty, there's no parent to attach to — the new node is the root, so handle that before the loop. This is the one branch the recursive version folds neatly into its base case but the iterative version must spell out.

Same shape as the recursion. Both follow one root-to-leaf path; the iterative form just replaces the implicit call-stack bookkeeping with an explicit parent pointer, trading O(h) stack space for O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

BST = [4,2,7,1,3], insert 6

Trailing parent pointer

How to read it:parent lags one node behind cur; when cur hits null, parent adopts the new leaf.

Rendering diagram…

Final result6 is the left child of 7

C · Code with teaching comments

Reference implementation previewpublic Node insert(Node root, int v) { Node node = new Node(v); if (root == null) return node; // empty tree → new node is root Node parent = null; Node cur = root;Explore the full code

solution.javaJava

Iterative Insert — Track the Parent — reference

4 teaching notes

1
public Node insert(Node root, int v) {
2
    Node node = new Node(v);
3
    if (root == null) return node;          // empty tree → new node is root
4
    Node parent = null;
5
    Node cur = root;
6
    boolean goLeft = false;
7
    while (cur != null) {                    // descend to a null slot
8
        // Trailing pointer — parent stays one step behind cur.
9
        parent = cur;
10
        if (v < cur.data) {
11
            cur = cur.left;
12
            goLeft = true;
13
        } else {
14
            cur = cur.right;
15
            goLeft = false;
16
        }
17
    }
18
    if (goLeft) parent.left = node;          // attach on the recorded side
19
    else parent.right = node;
20
    return root;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(h) timeO(1) spaceOpen the invariant and proofExplore the proof

Iterative tree insertion is the 'trailing pointer' technique: keep a parent one step behind the current node so that when current falls off the tree, you still hold the node to attach to. The same trailing-pointer idea reappears in linked-list deletion.

ComplexityO(h) time, O(1) space — A single descent along one root-to-leaf path → O(h) time. Only a couple of pointers are kept → O(1) extra space (no recursion stack).

E · Edge cases and pitfalls6BST = [], insert 5 — root null → return the new node directly.Explore edge cases

Edge cases handled

BST = [], insert 5root null → return the new node directly.
Insert smaller than allDescends fully left; parent is the leftmost node, side=left.
Insert larger than allDescends fully right; attaches as the rightmost leaf.

Pitfalls

Forgetting the empty-tree check — parent stays null and you NPE on attach.
Not recording which side you descended — you can't tell after cur is null.
Re-deriving the side incorrectly (e.g. using < where the descent used <=).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Calling insert without reassigning the link

If you call insert(root.left, v) but don't store the result back into root.left, the new node is created in the base case and immediately discarded — the tree is unchanged.

Explore the code comparison

Don't write this

if (v < root.data) {
    insert(root.left, v);    // return value dropped → node orphaned
}

Write this instead

if (v < root.data) {
    root.left = insert(root.left, v);  // reattach the subtree
}

Missing empty-tree handling (iterative)

When root is null there is no parent to attach to; the loop body would dereference a null parent. Handle the empty tree before descending.

Explore the code comparison

Don't write this

def insert(root, v):
    node = Node(v)
    parent, cur = None, root
    while cur:
        ...
    # parent is still None if tree was empty -> crash
    parent.left = node

Write this instead

def insert(root, v):
    node = Node(v)
    if root is None:
        return node      # empty tree handled first
    parent, cur = None, root
    while cur:
        ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BST descent: compare, branch left/right, attach at the null spot

Code pattern to memorize

insert(root, v):
    if root is null: return new Node(v)
    if v < root.data: root.left = insert(root.left, v)
    else: root.right = insert(root.right, v)
    return root

Rules to remember

1Smaller values go left, larger go right — the BST ordering invariant.
2A standard BST insert always lands the new value as a leaf (at the first null spot).
3Recursion returns the (possibly new) subtree root so the parent's link gets reattached.
4The base case root == null is where the new node is actually created.
5Don't rebuild or rebalance — plain BST insert just hangs the node at the empty slot it found.

Use this pattern when

Building a BST one value at a time from a stream of inserts
Any ordered structure where you locate position by comparison and attach at a leaf
A warm-up before deletion, search, or self-balancing trees

Choose another pattern when

You need guaranteed O(log n) under adversarial inserts → self-balancing tree (AVL / Red-Black)
Duplicates must be counted, not dropped → store a count field or define a tie-break side
You need order statistics → augment nodes with subtree sizes

Interview takeaway

BST insertion is binary search that ends in a creation: compare your way down to the null spot and hang the new node there. The recursion's 'return the subtree root and let the parent reattach' pattern is the same plumbing used by BST delete and many tree rewrites.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBST descent by comparison terminating in a node creation. The recursive 'return the subtree root and let the parent reassign the child link' idiom is the shared plumbing for BST insert, delete, and search; the iterative trailing-parent-pointer version trades stack space for O(1) extra space. Cost is O(h), motivating self-balancing trees under skew.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Is This a Binary Search Tree?
Validate the invariant insertion preserves, using min/max bounds.
Delete Node in a BST
Coming soon
Same descend-and-reattach idiom, but removal needs the inorder successor for two-child nodes.
Search in a BST
Coming soon
Identical descent without the creation step — return the node when values match.
Binary Search Tree: Lowest Common Ancestor
Descent by comparison again — split where the two targets diverge.

Same pattern

←

Maximum Weight Independent Set on a Tree

Continue · Next problem

Binary Search Tree: Lowest Common Ancestor

easyTreesFrequently asked

Binary Search Tree: Insertion

Trees & BST · 31 of 41 · 7 min

Given the root of a binary search tree and a value v, insert v into the BST and return the root of the updated tree.

A binary search tree keeps, for every node, all smaller values in its left subtree and all larger values in its right subtree. You may assume v is not already present.

In plain English

Examples

Example 1

Input: BST = [4,2,7,1,3], insert 6
Output: 6 becomes the left child of 7
Note: 6 > 4 → go right to 7. 6 < 7 → go left; 7's left is null → insert 6 there.

Example 2

Input: BST = [], insert 5
Output: 5 becomes the root
Note: Empty tree — the new node is the root (base case).

Example 3

Input: BST = [4,2,7,1,3], insert 0
Output: 0 becomes the left child of 1
Note: 0 < 4 → left to 2; 0 < 2 → left to 1; 0 < 1 → left null → insert.

Constraints

0 ≤ number of nodes ≤ 500 (the tree may be empty)
1 ≤ node value ≤ 500
The value to insert is not already in the tree
The BST ordering invariant holds before insertion

Clarifying questions4First question: Can the tree be empty?Explore questions

Q1.Can the tree be empty?
Yes. If root is null, the inserted node becomes the new root — that's the recursion's base case.
Q2.Can the value already exist?
The problem says values are unique. If duplicates were allowed, you'd decide a consistent side (usually right) or store a count instead of a new node.
Q3.Does the tree need to stay balanced?
No — a plain BST insert doesn't rebalance. The new node is hung at a leaf, so worst-case height can degrade to O(n). Self-balancing trees solve that separately.
Q4.Where does the new node end up?
Always as a leaf — the first null child slot the comparisons lead you to.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you understand the BST ordering invariant and can descend by comparison to the correct null slot, returning the reattached subtree.

Where candidates slip

Forgetting to return/reassign the subtree root (so the new node is created but never linked), or inserting at the root instead of at a leaf.

How to stand out

State that a plain BST insert always creates a leaf, give both the clean recursive form and an iterative parent-tracking version, and note the O(h) cost and why balancing matters under skew.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Insert — Return the Subtree Root (Optimal)Optimal	`O(h)`	`O(h)`	Start here. The 'return root and reassign' idiom is the cleanest and the most reusable.	Read
2	Iterative Insert — Track the Parent	`O(h)`	`O(1)`	Offer if recursion is discouraged or to show you can manage the parent link explicitly.	Read

Descent decision at each node

How to read it:Compare v with the current node, branch, and stop at the first null child.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Recursive Insert — Return the Subtree Root (Optimal)

TimeO(h)SpaceO(h)

Start here. The 'return root and reassign' idiom is the cleanest and the most reusable.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Where can a new value go so the BST invariant still holds? Compare it against the root: which subtree must it live in?

2Hint 2Explore hint

Recurse into the correct subtree. What does it mean when that subtree is null — where exactly does the value belong?

3Hint 3Explore hint

Base case: a null subtree means you've found the empty slot — return a new node. Otherwise recurse, reassign the child link, and return the current root.

A · Core idea

Why it's always a leaf. Because we only stop at a null child, the new node has no children of its own at insert time — it's a leaf. A plain BST insert never restructures existing nodes.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

BST = [4,2,7,1,3], insert 6

Inserting 6 into [4,2,7,1,3]

How to read it:Path 4 → 7 → (left null); 6 becomes 7's left child.

Rendering diagram…

Final result6 is the left child of 7

C · Code with teaching comments

solution.javaJava

Recursive Insert — Return the Subtree Root (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
class Node {
3
    int data;
4
    Node left;
5
    Node right;
6
    Node(int data) { this.data = data; }
7
}
8
 
9
public Node insert(Node root, int v) {
10
    if (root == null) return new Node(v);   // empty slot found → create
11
    if (v < root.data) {
12
        root.left = insert(root.left, v);   // reassign the left link
13
    } else {
14
        root.right = insert(root.right, v); // reassign the right link
15
    }
16
    return root;                            // hand this subtree back up
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(h) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6BST = [], insert 5 — root is null → return Node(5); it becomes the root.Explore edge cases

Edge cases handled

BST = [], insert 5root is null → return Node(5); it becomes the root.
Insert a value smaller than all nodesDescends fully left, attaches as the leftmost leaf.
Insert into a left-skewed chainPath length is O(n) — worst-case insertion cost.

Pitfalls

Calling insert(root.left, v) without assigning the result — node created but never linked.
Inserting at the root or an interior node instead of at the null leaf slot.
Mishandling duplicates when the problem allows them — pick a consistent side or a count.

03.2

Approach 2 of 2

Iterative Insert — Track the Parent

TimeO(h)SpaceO(1)

Offer if recursion is discouraged or to show you can manage the parent link explicitly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk down with two pointers: the current node and its parent. When current becomes null, the parent is where you attach.

2Hint 2Explore hint

Remember which side you descended (left or right) so you attach the new node on the correct side of the parent.

3Hint 3Explore hint

Handle the empty-tree case separately: if root is null, the new node is simply the root.

A · Core idea

The iterative version makes the descent explicit and uses no call stack, so its extra space is O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

BST = [4,2,7,1,3], insert 6

Trailing parent pointer

How to read it:parent lags one node behind cur; when cur hits null, parent adopts the new leaf.

Rendering diagram…

Final result6 is the left child of 7

C · Code with teaching comments

solution.javaJava

Iterative Insert — Track the Parent — reference

4 teaching notes

1
public Node insert(Node root, int v) {
2
    Node node = new Node(v);
3
    if (root == null) return node;          // empty tree → new node is root
4
    Node parent = null;
5
    Node cur = root;
6
    boolean goLeft = false;
7
    while (cur != null) {                    // descend to a null slot
8
        // Trailing pointer — parent stays one step behind cur.
9
        parent = cur;
10
        if (v < cur.data) {
11
            cur = cur.left;
12
            goLeft = true;
13
        } else {
14
            cur = cur.right;
15
            goLeft = false;
16
        }
17
    }
18
    if (goLeft) parent.left = node;          // attach on the recorded side
19
    else parent.right = node;
20
    return root;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(h) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(h) time, O(1) space — A single descent along one root-to-leaf path → O(h) time. Only a couple of pointers are kept → O(1) extra space (no recursion stack).

E · Edge cases and pitfalls6BST = [], insert 5 — root null → return the new node directly.Explore edge cases

Edge cases handled

BST = [], insert 5root null → return the new node directly.
Insert smaller than allDescends fully left; parent is the leftmost node, side=left.
Insert larger than allDescends fully right; attaches as the rightmost leaf.

Pitfalls

Forgetting the empty-tree check — parent stays null and you NPE on attach.
Not recording which side you descended — you can't tell after cur is null.
Re-deriving the side incorrectly (e.g. using < where the descent used <=).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. class Node { int data; Node left; Node right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Calling insert without reassigning the link

If you call insert(root.left, v) but don't store the result back into root.left, the new node is created in the base case and immediately discarded — the tree is unchanged.

Explore the code comparison

Don't write this

if (v < root.data) {
    insert(root.left, v);    // return value dropped → node orphaned
}

Write this instead

if (v < root.data) {
    root.left = insert(root.left, v);  // reattach the subtree
}

Missing empty-tree handling (iterative)

When root is null there is no parent to attach to; the loop body would dereference a null parent. Handle the empty tree before descending.

Explore the code comparison

Don't write this

def insert(root, v):
    node = Node(v)
    parent, cur = None, root
    while cur:
        ...
    # parent is still None if tree was empty -> crash
    parent.left = node

Write this instead

def insert(root, v):
    node = Node(v)
    if root is None:
        return node      # empty tree handled first
    parent, cur = None, root
    while cur:
        ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BST descent: compare, branch left/right, attach at the null spot

Code pattern to memorize

insert(root, v):
    if root is null: return new Node(v)
    if v < root.data: root.left = insert(root.left, v)
    else: root.right = insert(root.right, v)
    return root

Rules to remember

1Smaller values go left, larger go right — the BST ordering invariant.
2A standard BST insert always lands the new value as a leaf (at the first null spot).
3Recursion returns the (possibly new) subtree root so the parent's link gets reattached.
4The base case root == null is where the new node is actually created.
5Don't rebuild or rebalance — plain BST insert just hangs the node at the empty slot it found.

Use this pattern when

Building a BST one value at a time from a stream of inserts
Any ordered structure where you locate position by comparison and attach at a leaf
A warm-up before deletion, search, or self-balancing trees

Choose another pattern when

You need guaranteed O(log n) under adversarial inserts → self-balancing tree (AVL / Red-Black)
Duplicates must be counted, not dropped → store a count field or define a tie-break side
You need order statistics → augment nodes with subtree sizes

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Is This a Binary Search Tree?
Validate the invariant insertion preserves, using min/max bounds.
Delete Node in a BST
Coming soon
Same descend-and-reattach idiom, but removal needs the inorder successor for two-child nodes.
Search in a BST
Coming soon
Identical descent without the creation step — return the node when values match.
Binary Search Tree: Lowest Common Ancestor
Descent by comparison again — split where the two targets diverge.

Same pattern

←

Maximum Weight Independent Set on a Tree

Continue · Next problem

Binary Search Tree: Lowest Common Ancestor