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. You are given a binary search tree and two nodes within it. You need to find the node that is the deepest ancestor common to both nodes, leveraging the BST property to optimize the search. Which approach guarantees the most efficient solution?

easy

A. Perform two separate DFS traversals to find paths from root to each node, then compare paths to find the last common node.

B. Apply dynamic programming to store ancestors of each node and then find the lowest common ancestor by comparing stored data.

C. Iteratively traverse the BST from the root, moving left or right depending on the values of the two nodes relative to the current node, stopping when the current node splits the paths to the two nodes.

D. Use a greedy approach that always moves towards the node with the smaller value until both nodes are found.

Solution

1. Step 1: Understand BST property usage

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows pruning the search space efficiently.

2. Step 2: Identify optimal traversal

   Starting from root, if both target nodes are smaller, go left; if both are larger, go right; else current node is the split point and thus the LCA.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative BST traversal uses O(h) time and O(1) space [OK]

Hint: Use BST property to prune search paths [OK]

Common Mistakes:

• Using path comparison wastes time and space
• Greedy approach ignores split point logic
• Dynamic programming is unnecessary overhead

2. Consider the following buggy code for trimming a BST. Which line contains the subtle bug that can cause the resulting tree to violate BST properties or cause runtime errors?

medium

A. Line 3: root = root.left when root.val < low

B. Line 5: root = root.left when root.val > high

C. Line 10: cur.left = cur.left.right inside left subtree trimming

D. Line 16: cur.right = cur.right.left inside right subtree trimming

Solution

1. Step 1: Check root adjustment logic

   If root.val < low, root should move to root.right, not root.left, to find valid nodes.

2. Step 2: Verify other lines

   Line 5 correctly moves root to root.left if root.val > high. Lines 10 and 16 correctly adjust subtree pointers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect pointer move causes invalid pruning or infinite loop [OK]

Hint: Root moves wrong direction when value < low [OK]

Common Mistakes:

• Confusing left and right subtree moves
• Incorrect pointer updates causing invalid BST

3. 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

4. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity

5. Suppose the BST can contain duplicate values and you want to find if there exist two nodes (not necessarily distinct) whose values sum to k. Which modification to the optimal inorder + two-pointer approach correctly handles this scenario?

hard

A. Perform inorder traversal and remove duplicates before applying two-pointer technique.

B. Use the same two-pointer approach but allow left and right pointers to point to the same index.

C. Use a hash set to store values and check complements, ignoring duplicates.

D. During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST.

Solution

1. Step 1: Understand duplicates and two-pointer constraints

   Two-pointer approach requires two distinct indices; if pointers meet, need to verify if duplicate values exist.

2. Step 2: Modify check when left == right

   Check if the value at that index occurs at least twice in the BST to allow sum with itself.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only During two-pointer traversal, if left == right, check if the value at that index appears at least twice in the BST. correctly handles duplicates without breaking two-pointer logic [OK]

Hint: Check duplicates count when pointers meet [OK]

Common Mistakes:

• Allowing pointers to be equal without duplicate check
• Removing duplicates loses valid pairs
• Ignoring duplicates in hash set approach