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.