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.