BST Insert Operation in DSA C++ - Execution Trace

Concept Flow - BST Insert Operation

Create new node

↓

Start at root

↓

Compare new value with current node

↓

Go left

↓

Is child null?

↓

Insert new node

Insert starts at root, compares value, moves left or right until a null child is found, then inserts the new node there.

Execution Sample

DSA C++

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* insert(Node* root, int val) {
  if (!root) return new Node{val, nullptr, nullptr};
  if (val < root->data) root->left = insert(root->left, val);
  else root->right = insert(root->right, val);
  return root;
}

This code inserts a value into a BST by recursively finding the correct position.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Create new node with value 25	null	N/A	newNode = Node(25)	∅
2	Start at root	20	25 > 20	current = root (20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ data:40│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ └────────┘ └────────┘ └────────┘ root
3	Move right since 25 > 20	30	25 < 30	current = current->left (null)	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ data:40│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ └────────┘ └────────┘ └────────┘ root
4	Left child of 30 is null, insert here	null	N/A	30->left = newNode (25)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ data:40│ │ data:25│ │ left:──┼──→ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ │ right:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ root
5	Return updated root	20	N/A	No pointer change at root	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:30│ │ data:40│ │ data:25│ │ left:──┼──→ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ │ right:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ root

💡 Insertion complete when a null child pointer is replaced with the new node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
root	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)
current	null	null	Node(20)	Node(30)	null	null
newNode	null	Node(25)	Node(25)	Node(25)	Node(25)	Node(25)
30->left	null	null	null	null	Node(25)	Node(25)

Key Moments - 3 Insights

Why do we move left or right based on comparison instead of inserting immediately?

Because the BST property requires left children to be smaller and right children to be larger or equal. The execution_table rows 2 and 3 show how we compare and move accordingly until we find a null child to insert.

What happens if the tree is empty at the start?

Step 1 shows creating a new node when root is null. The new node becomes the root, as there is no existing tree.

Why do we assign the returned node to root->left or root->right?

Because the insert function is recursive and returns the updated subtree root. Assigning ensures the parent's pointer updates if a new node is inserted deeper, as shown in step 4 where 30->left is assigned the new node.

Visual Quiz - 3 Questions

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

A Node with value 30

B Node with value 20

C Null

D Node with value 25

💡 Hint

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

At which step does the new node get linked into the tree?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for the step where 'Pointer Changes' shows assignment of newNode to a child pointer.

If the inserted value was 35 instead of 25, which direction would the traversal go at Step 2?

A Left

B Right

C Stay at root

D Insert immediately

💡 Hint

Refer to the comparison logic in Step 2 where value is compared to current node.

Concept Snapshot

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

Full Transcript

The BST insert operation begins by creating a new node with the value to insert. Starting at the root, the algorithm compares the new value with the current node's data. If the new value is smaller, it moves to the left child; if larger or equal, it moves to the right child. This process repeats until it finds a null child pointer, where it inserts the new node. The recursive insert function returns the updated subtree root to maintain correct parent pointers. This ensures the binary search tree property is preserved, allowing efficient search operations.