Insert into a BST

📋

Problem

Imagine you are maintaining a sorted phone directory stored as a binary search tree. When a new contact is added, you need to insert it in the correct position to keep the directory organized.

Given the root node of a binary search tree (BST) and a value to insert into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. The insertion must maintain the BST property.

The number of nodes in the tree is in the range [0, 10^5].-10^8 <= Node.val <= 10^8All the values Node.val are unique.val does not exist in the original BST.

Edge cases: Empty tree (root = null) → new node becomes rootInsert value smaller than all existing nodes → inserted as leftmost leafInsert value larger than all existing nodes → inserted as rightmost leaf

</>

IDE

def insertIntoBST(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:public TreeNode insertIntoBST(TreeNode root, int val)TreeNode* insertIntoBST(TreeNode* root, int val)function insertIntoBST(root, val)

def insertIntoBST(root, val):
    # Write your solution here
    pass

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

TreeNode* insertIntoBST(TreeNode* root, int val) {
    // Write your solution here
    return nullptr;
}

function insertIntoBST(root, val) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [4,2,7,1,3]Did not insert the new node at all; returned original tree unchanged.✅ Ensure to create and attach a new node when the correct null child is found during traversal.

Wrong: [4,2,7,1,3,7]Inserted duplicate node or reused existing node incorrectly.✅ Create a new node with val and insert it only once at the correct null child position.

Wrong: [10,5,15,1,3]Inserted new node at wrong subtree or replaced existing nodes incorrectly.✅ Traverse correctly comparing val with node values and insert at null child without overwriting existing nodes.

Wrong: nullDid not handle empty tree input; returned null instead of new node.✅ Return new TreeNode(val) when root is null.

Wrong: [10,5,15,1,7]Inserted new node at wrong child (right child of 5 instead of left child of 7).✅ Continue traversal until correct leaf is found; check both left and right children properly.

✓

Test Cases

Try testing your code with empty trees and single-node trees to catch base case bugs.

Consider tricky insertion positions that might fool greedy or partial traversal approaches.

Think about the time complexity of your insertion method on large balanced trees.

t1_01basic

Input{"root":[4,2,7,1,3],"val":5}

Expected[4,2,7,1,3,5]

⏱ Performance - must finish in 2000ms

Starting at root 4, since 5 > 4, go right to 7. Since 5 < 7, insert 5 as left child of 7.

💡 Traverse the BST comparing val with current node values to find the correct leaf position.

💡 Use recursion or iteration to move left if val < node.val, else move right until a null child is found.

💡 Insert the new node as the left or right child where the traversal ends.

Why it failed: Failed to insert at correct position; likely did not traverse properly or did not assign new node correctly. Fix by ensuring traversal continues until null child and then insert new node there.

✓ Correct insertion maintaining BST property.

t1_02basic

Input{"root":[10,5,15,null,null,12,20],"val":13}

Expected[10,5,15,null,null,12,20,null,null,null,13]

⏱ Performance - must finish in 2000ms

Traverse from 10 to 15, then to 12; since 13 > 12, insert 13 as right child of 12.

💡 Follow BST property to decide left or right traversal at each node.

💡 Check if current node's left or right child is null before inserting.

💡 Insert new node as right child of 12 since 13 > 12 and 12's right child is null.

Why it failed: Incorrect insertion position; possibly inserted at wrong subtree or overwrote existing nodes. Fix by checking child pointers before insertion.

✓ Insertion correctly placed as right child of 12.

t2_01edge

Input{"root":[],"val":42}

Expected[42]

⏱ Performance - must finish in 2000ms

Empty tree; new node with val 42 becomes the root.

💡 Check if root is null before traversal.

💡 If root is null, return new node with val as root.

💡 Insert new node directly when tree is empty.

Why it failed: Did not handle empty tree case; must return new node as root when root is null.

✓ Correctly handled empty tree insertion.

t2_02edge

Input{"root":[10,5,15],"val":1}

Expected[10,5,15,1]

⏱ Performance - must finish in 2000ms

Insert value smaller than all existing nodes; inserted as leftmost leaf under 5.

💡 Traverse left subtree when val < node.val.

💡 Continue until left child is null to insert new node.

💡 Insert new node as left child of 5.

Why it failed: Failed to insert as leftmost leaf; likely stopped traversal too early or inserted incorrectly.

✓ Correctly inserted as leftmost leaf.

t2_03edge

Input{"root":[10,5,15],"val":20}

Expected[10,5,15,null,null,null,20]

⏱ Performance - must finish in 2000ms

Insert value larger than all existing nodes; inserted as rightmost leaf under 15.

💡 Traverse right subtree when val > node.val.

💡 Continue until right child is null to insert new node.

💡 Insert new node as right child of 15.

Why it failed: Failed to insert as rightmost leaf; likely stopped traversal too early or inserted incorrectly.

✓ Correctly inserted as rightmost leaf.

t3_01corner

Input{"root":[8,3,10,1,6,null,14,null,null,4,7,13],"val":5}

Expected[8,3,10,1,6,null,14,null,null,4,7,13,null,5]

⏱ Performance - must finish in 2000ms

Insertion between nodes 4 and 6; inserted as right child of 4 maintaining BST property.

💡 Do not greedily insert at first null child encountered; continue traversal to correct leaf.

💡 Traverse left or right based on comparison until null child is found.

💡 Insert new node as right child of 4, not as child of 6 or 3.

Why it failed: Greedy insertion bug: inserted at first null child instead of correct leaf. Fix by continuing traversal until proper leaf is found.

✓ Correctly inserted between nodes maintaining BST property.

t3_02corner

Input{"root":[5],"val":3}

Expected[5,3]

⏱ Performance - must finish in 2000ms

Single node tree; inserted smaller value as left child.

💡 Handle single node trees correctly.

💡 Check if left or right child is null before insertion.

💡 Insert new node as left child of root.

Why it failed: Confused 0/1 insertion with unbounded insertion; inserted multiple nodes or incorrect subtree. Fix by inserting exactly one node at correct leaf.

✓ Correctly inserted single node in single-node tree.

t3_03corner

Input{"root":[10,5,15,2,7,null,20],"val":6}

Expected[10,5,15,2,7,null,20,null,null,6]

⏱ Performance - must finish in 2000ms

Inserted 6 as left child of 7; tests off-by-one errors in traversal.

💡 Ensure traversal does not stop prematurely at node 7.

💡 Check left child of 7 is null before insertion.

💡 Insert new node as left child of 7.

Why it failed: Off-by-one traversal error: inserted at wrong node or wrong child. Fix by correctly checking child pointers before insertion.

✓ Correctly inserted node at intended leaf.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218],"val":123456}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced BST with 100 nodes; insertion must complete in O(h) time where h ~ log n.

💡 Insertion should be O(h) where h is tree height, not O(n).

💡 Use iterative or recursive traversal to find insertion point efficiently.

💡 Avoid unnecessary traversals or copying of nodes.

Why it failed: TLE due to inefficient traversal or rebuilding entire tree; fix by using O(h) traversal to insert without full tree reconstruction.

✓ Efficient O(h) insertion confirmed.

Practice

1. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

2. You are given a binary tree and need to determine if it satisfies the property that for every node, all nodes in its left subtree have smaller values and all nodes in its right subtree have larger values, with no duplicates allowed. Which approach guarantees an optimal solution to this problem?

easy

A. Check each node by comparing it only with its immediate children recursively.

B. Apply a greedy algorithm that validates nodes as soon as they are visited.

C. Use dynamic programming to store subtree min and max values and combine results bottom-up.

D. Perform an inorder traversal and verify that the node values are strictly increasing.

Solution

1. Step 1: Understand BST property

   The BST property requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater, strictly increasing in inorder traversal.

2. Step 2: Recognize inorder traversal pattern

   Inorder traversal of a valid BST produces a strictly increasing sequence of values, so verifying this sequence guarantees correctness efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Inorder traversal yields sorted values for BST [OK]

Hint: Inorder traversal of BST is strictly increasing [OK]

Common Mistakes:

• Only comparing node with immediate children
• Using greedy checks without global ordering
• Confusing subtree min/max with inorder sequence

3. What is the average time complexity per call of next() in the Morris traversal based BST Iterator, assuming the BST has n nodes?

medium

A. O(1) amortized per next() call because each edge is visited at most twice.

B. O(n) per next() call because each call may traverse the entire tree.

C. O(h) per next() call where h is the tree height due to traversing left children.

D. O(log n) per next() call assuming a balanced BST and stack usage.

Solution

1. Step 1: Understand Morris traversal edge visits

   Each edge in the BST is visited at most twice: once to create a thread and once to remove it.

2. Step 2: Calculate amortized cost per next()

   Since total work is O(n) for n nodes, and there are n calls to next(), average cost per call is O(1) amortized.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per next() matches Morris traversal properties [OK]

Hint: Morris traversal visits edges twice total [OK]

Common Mistakes:

• Assuming worst-case O(n) per call
• Confusing with stack-based O(h)
• Ignoring amortized analysis

4. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children

5. Suppose you want to balance a BST but now the tree nodes can have duplicate values and the BST property is relaxed to allow duplicates on either side. Which modification to the balancing algorithm ensures the resulting tree remains valid and balanced?

hard

A. Use preorder traversal instead of inorder to collect nodes, then rebuild.

B. Modify the middle index calculation to always pick the left middle to keep duplicates on left.

C. During inorder traversal, collect nodes preserving duplicates order, then choose middle node as root as usual.

D. Sort the collected nodes by value before rebuilding to handle duplicates properly.

Solution

1. Step 1: Understand duplicates in BST with relaxed property

   Inorder traversal still produces nodes in non-decreasing order preserving duplicates order.

2. Step 2: Rebuild balanced BST using middle node selection

   Choosing middle node as root maintains balance and respects duplicates order.

3. Step 3: Avoid sorting or preorder traversal

   Sorting is unnecessary and preorder breaks sorted order; left middle bias skews balance.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inorder traversal + middle node rebuild works with duplicates [OK]

Hint: Inorder traversal preserves duplicates order for balanced rebuild [OK]

Common Mistakes:

• Using preorder traversal losing sorted order
• Sorting nodes again causing unnecessary overhead
• Biasing middle index causing unbalanced tree