BST Insert Operation in DSA Typescript - Execution Trace

Concept Flow - BST Insert Operation

Create new node

↓

Start at root

↓

Compare new value with current node

↓

Go left

↓

Is child null?

No→Move to child node

Yes↓

Insert new node here

↓

Done

Insert a new value by comparing from root, moving left or right until a null child is found, then insert the new node there.

Execution Sample

DSA Typescript

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

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

This code inserts a value into a BST by recursively finding the correct spot and adding a new node.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Create new node with value 25	null	N/A	newNode = Node(25)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼─→ │ left:∅ │ │ right:─┼─→┐ │ right:─┼─→ │ right:∅│ │ │ │ └────────┘ └────────┘ └────────┘ root
2	Start at root	30	25 < 30? Yes	current = root (30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼─→ │ left:∅ │ │ right:─┼─→┐ │ right:─┼─→ │ right:∅│ │ │ │ └────────┘ └────────┘ └────────┘ root
3	Go left from 30	20	25 < 20? No	current = 20	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼─→ │ left:∅ │ │ right:─┼─→┐ │ right:─┼─→ │ right:∅│ │ │ │ └────────┘ └────────┘ └────────┘ root
4	Go right from 20	null	Child is null, insert here	20.right = newNode(25)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:25│ │ data:40│ │ left:──┼─→ │ left:∅ │ │ left:∅ │ │ right:─┼─→┐ │ right:─┼─→ │ right:─┼─→ │ right:∅ │ │ │ │ └────────┘ └────────┘ └────────┘ └────────┘ root
5	Return to root	30	Insertion complete	No pointer changes	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:25│ │ data:40│ │ left:──┼─→ │ left:∅ │ │ left:∅ │ │ right:─┼─→┐ │ right:─┼─→ │ right:─┼─→ │ right:∅ │ │ │ │ └────────┘ └────────┘ └────────┘ └────────┘ root

💡 Insertion done when a null child is found and new node is linked.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
root	Node(30)	Node(30)	Node(30)	Node(30)	Node(30)
current	null	Node(30)	Node(20)	null	null
newNode	null	Node(25)	Node(25)	Node(25)	Node(25)
20.right	null	null	null	Node(25)	Node(25)

Key Moments - 3 Insights

Why do we insert the new node when the child pointer is null?

Because a null child means there is no node there yet, so it's the correct place to add the new node. See Step 4 in execution_table where current is null and insertion happens.

Why do we move left or right based on comparison?

BST property says left child is less than node, right child is greater or equal. So we compare new value with current node to decide direction. See Step 2 and 3 in execution_table.

What happens if the tree is empty (root is null)?

We create a new node and return it as the root. This is shown in Step 1 where newNode is created and root is null.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the current node's data?

A 20

B 30

C 25

D null

💡 Hint

Check the 'Current Node' column at Step 3 in execution_table.

At which step does the insertion of the new node actually happen?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'insert here' or pointer changes in execution_table.

If the new value was 35 instead of 25, which direction would the traversal go from root 30?

A Stay at root

B Left

C Right

D Insert at root

💡 Hint

Refer to the comparison logic in concept_flow and execution_table Step 2.

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- If less, go left; if greater or equal, go right
- Repeat until null child found
- Insert new node at null position
- Maintains BST property

Full Transcript

To insert a value in a Binary Search Tree (BST), we start at the root and compare the new value with the current node's data. If the new value is less, we move to the left child; if greater or equal, we move to the right child. We continue this until we find a null child pointer, which means there is no node there yet. At this point, we insert the new node by linking it to the parent's child pointer. This process maintains the BST property where left children are less than the node and right children are greater or equal. If the tree is empty, the new node becomes the root.

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