BST Insert Operation in DSA Typescript

Mental Model

A binary search tree keeps smaller values on the left and larger on the right. Inserting means finding the right empty spot following this rule.

Analogy: Imagine placing books on a shelf where all books with smaller titles go to the left side and bigger titles to the right. To add a new book, you walk down the shelf choosing left or right until you find an empty spot.

    10
   /  \
  5    15
 / \   / \
null null null null

Dry Run Walkthrough

Input: Insert value 12 into BST: 10 -> 5 -> null, 10 -> 15 -> null

Goal: Add 12 to the BST in the correct position to keep the order

Step 1: Start at root node 10

10 ↑ -> 5 -> null, 10 -> 15 -> null

Why: We always start insertion from the root to find the correct place

Step 2: Compare 12 with 10, move right to node 15

10 -> 5 -> null, 10 -> 15 ↑ -> null

Why: 12 is greater than 10, so we go right

Step 3: Compare 12 with 15, move left where null is found

10 -> 5 -> null, 10 -> 15 -> null ↑

Why: 12 is less than 15, so we go left to find empty spot

Step 4: Insert new node with value 12 at left of 15

10 -> 5 -> null, 10 -> 15 -> 12 -> null

Why: Found empty spot, insert here to keep BST order

Result:

10 -> 5 -> null, 10 -> 15 -> 12 -> null

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function insertIntoBST(root: TreeNode | null, val: number): TreeNode {
  if (root === null) {
    return new TreeNode(val); // insert here if spot is empty
  }
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val); // go left
  } else {
    root.right = insertIntoBST(root.right, val); // go right
  }
  return root; // return unchanged root
}

function printBST(root: TreeNode | null): string {
  if (root === null) return "null";
  const leftStr = printBST(root.left);
  const rightStr = printBST(root.right);
  return `${root.val} -> ${leftStr}, ${root.val} -> ${rightStr}`;
}

// Driver code
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
const newRoot = insertIntoBST(root, 12);
console.log(printBST(newRoot));

if (root === null) { return new TreeNode(val); }

insert new node when empty spot found

if (val < root.val) { root.left = insertIntoBST(root.left, val); }

go left if value is smaller

else { root.right = insertIntoBST(root.right, val); }

go right if value is bigger or equal

return root;

return current root to link back after insertion

Output

10 -> 5 -> null, 10 -> null, 10 -> 15 -> 12 -> null, 12 -> null, 15 -> null

Complexity Analysis

Time: O(h) where h is the height of the tree because we follow one path down to insert

Space: O(h) due to recursion stack in worst case equal to tree height

vs Alternative: Compared to inserting in an unsorted tree which is O(1), BST insert is slower but keeps data ordered for fast search

Edge Cases

Empty tree (root is null)

New node becomes the root

DSA Typescript

if (root === null) { return new TreeNode(val); }

Insert value smaller than all nodes

Traverse left until null and insert there

DSA Typescript

if (val < root.val) { root.left = insertIntoBST(root.left, val); }

Insert value larger than all nodes

Traverse right until null and insert there

DSA Typescript

else { root.right = insertIntoBST(root.right, val); }

When to Use This Pattern

When you need to add a value to a sorted tree structure and keep order, use BST insert to find the correct spot by comparing values.

Common Mistakes

Mistake: Inserting without checking if current node is null, causing errors
Fix: Always check if current node is null to insert new node there

Mistake: Not linking the inserted node back to parent, losing the new node
Fix: Assign the result of recursive insert back to left or right child pointer

Summary

Inserts a new value into the binary search tree while keeping it ordered.

Use when you want to add data to a BST and maintain its sorted property.

The key is to follow left or right pointers based on comparisons until you find an empty spot.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new node while keeping the BST property intact

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST property

   A BST keeps nodes ordered so that left child is smaller and right child is larger than the parent.

2. Step 2: Purpose of insert operation

   Insert adds a new node in the correct position to maintain this order.

3. Final Answer:

   To add a new node while keeping the BST property intact -> Option A

4. Quick Check:

   Insert = Add node maintaining order [OK]

Hint: Insert adds nodes without breaking BST order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert finds max or min values

2. Which of the following is the correct TypeScript function signature for inserting a value into a BST node?

easy

A. function insert(root: Node, value: number): void

B. function insert(value: number, root: Node): void

C. function insert(root: Node | null, value: number): Node | null

D. function insert(root: Node, value: string): Node

Solution

1. Step 1: Analyze parameter types

   Insert needs the root node (which can be null if tree is empty) and the value to insert (a number).

2. Step 2: Analyze return type

   It returns the updated root node (Node or null if empty).

3. Final Answer:

   function insert(root: Node | null, value: number): Node | null -> Option C

4. Quick Check:

   Correct params and return type [OK]

Hint: Insert returns updated root, accepts root or null [OK]

Common Mistakes:

• Swapping parameter order
• Using void return type instead of returning Node
• Using wrong value type like string

3. Given the following BST and the insert operation call insert(root, 7), what will be the in-order traversal of the BST after insertion?

Initial BST in-order: 3 -> 5 -> 8 -> 10

Code snippet:

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

medium

A. [3, 5, 8, 7, 10]

B. [3, 5, 8, 10, 7]

C. [7, 3, 5, 8, 10]

D. [3, 5, 7, 8, 10]

Solution

1. Step 1: Locate insertion point for 7

   7 is greater than 5 but less than 8, so it goes to the left of 8.

2. Step 2: Perform in-order traversal after insertion

   In-order visits left, root, right: 3, 5, 7, 8, 10.

3. Final Answer:

   [3, 5, 7, 8, 10] -> Option D

4. Quick Check:

   In-order sorted after insert [OK]

Hint: Insert left if smaller, right if larger [OK]

Common Mistakes:

• Placing 7 incorrectly after 8
• Confusing in-order traversal order
• Ignoring recursive insert logic

4. The following TypeScript code attempts to insert a value into a BST but has a bug. What is the error?

function insert(root: Node | null, val: number): Node {
  if (root === null) {
    return new Node(val);
  }
  if (val <= root.val) {
    insert(root.left, val);
  } else {
    insert(root.right, val);
  }
  return root;
}

medium

A. The base case is missing

B. The recursive calls do not update root.left or root.right

C. The function returns void instead of Node

D. The comparison operator should be < instead of <=

Solution

1. Step 1: Check recursive calls

   The calls to insert do not assign the result back to root.left or root.right, so tree structure is not updated.

2. Step 2: Correct recursive assignment

   Should be root.left = insert(root.left, val) or root.right = insert(root.right, val) to update links.

3. Final Answer:

   The recursive calls do not update root.left or root.right -> Option B

4. Quick Check:

   Must assign recursive insert result to child [OK]

Hint: Always assign recursive insert result to child node [OK]

Common Mistakes:

• Forgetting to assign recursive call result
• Misunderstanding base case presence
• Changing comparison operator unnecessarily

5. You have a BST with nodes 10, 5, 15, 3, 7, 12, 18. You want to insert 6. Which sequence of nodes will you visit during the insert operation?

hard

A. [10, 5, 7]

B. [10, 15, 12]

C. [10, 5, 3]

D. [10, 15, 18]

Solution

1. Step 1: Start at root 10

   6 is less than 10, so move to left child 5.

2. Step 2: Compare with 5 and 7

   6 is greater than 5, move to right child 7. 6 is less than 7, so insert here.

3. Final Answer:

   [10, 5, 7] -> Option A

4. Quick Check:

   Traverse nodes comparing 6 until insertion point [OK]

Hint: Follow left/right based on comparison until null [OK]

Common Mistakes:

• Visiting wrong subtree based on comparison
• Skipping nodes in path
• Confusing insertion path with traversal order