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.

Practice

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

easy

A. To delete a node from the BST

B. To find the height of the BST

C. To add a new node while maintaining BST properties

D. To traverse the BST in order

Solution

1. Step 1: Understand BST insert operation

   The insert operation adds a new node to the BST while keeping the order property intact: left child < parent < right child.

2. Step 2: Differentiate from other operations

   Deleting nodes, finding height, or traversing are different operations and do not describe insertion.

3. Final Answer:

   To add a new node while maintaining BST properties -> Option C

4. Quick Check:

   Insert = Add node maintaining order [OK]

Hint: Insert means add node keeping BST order intact [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert changes tree height only
• Mixing insert with traversal methods

2. Which of the following is the correct syntax to insert a value val into a BST using a recursive function in C++?

easy

A. root = insert(root, val);

B. insert(root, val);

C. root.insert(val);

D. insert(val, root);

Solution

1. Step 1: Understand recursive insert signature

   Recursive insert usually returns the new root after insertion, so assignment like root = insert(root, val); is needed.

2. Step 2: Check other options

   Calling insert(root, val); without assignment ignores updated root. root.insert(val); assumes method on node object which is uncommon. insert(val, root); has wrong parameter order.

3. Final Answer:

   root = insert(root, val); -> Option A

4. Quick Check:

   Assign returned root after insert [OK]

Hint: Assign root = insert(root, val) for recursive insertion [OK]

Common Mistakes:

• Not assigning the returned root after insertion
• Using wrong parameter order in insert call
• Assuming insert is a method of node object

3. Consider the following C++ code inserting values into an empty BST:

struct Node {
  int data;
  Node* left;
  Node* right;
  Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
  Node* root = nullptr;
  root = insert(root, 10);
  root = insert(root, 5);
  root = insert(root, 15);
  root = insert(root, 12);
  return 0;
}

What is the structure of the BST after these insertions?

medium

A. 10 -> 5 -> 12 (left), 10 -> 15 -> null (right subtree)

B. 10 -> 15 -> null (left), 10 -> 5 -> 12 (right subtree)

C. 10 -> 12 -> 5 (left), 10 -> 15 -> null (right subtree)

D. 10 -> 5 -> null (left), 10 -> 15 -> 12 (right subtree)

Solution

1. Step 1: Insert 10, 5, 15, 12 step-by-step

   Start with empty root. Insert 10 as root. Insert 5 goes left of 10. Insert 15 goes right of 10. Insert 12 goes left of 15.

2. Step 2: Visualize BST structure

   Root 10 has left child 5 (no children), right child 15 with left child 12 (no right child).

3. Final Answer:

   10 -> 5 -> null (left), 10 -> 15 -> 12 (right subtree) -> Option D

4. Quick Check:

   Insert order builds left 5, right 15 with left 12 [OK]

Hint: Insert smaller left, larger right; 12 is left child of 15 [OK]

Common Mistakes:

• Placing 12 as right child of 15 instead of left
• Swapping left and right children of 10
• Ignoring null children in output

4. The following code attempts to insert a value into a BST but causes a runtime error:

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

What is the error and how to fix it?

medium

A. Missing return after creating new node; add return newNode;

B. Incorrect comparison operator; use <= instead of <

C. Should not assign to root->left or root->right

D. Node constructor is missing initialization

Solution

1. Step 1: Identify missing return in base case

   When root is nullptr, new node is created but not returned, so function continues and dereferences nullptr causing runtime error.

2. Step 2: Fix by returning new node immediately

   Add return newNode; inside the if block to return the newly created node and stop further execution.

3. Final Answer:

   Missing return after creating new node; add return newNode; -> Option A

4. Quick Check:

   Return new node on nullptr base case [OK]

Hint: Always return new node immediately when root is nullptr [OK]

Common Mistakes:

• Not returning new node causes nullptr dereference
• Changing comparison operator unnecessarily
• Misunderstanding pointer assignments

5. You have a BST with nodes 20, 10, 30, 25, 40. You want to insert 15 and 35. After insertion, which of the following is the correct in-order traversal of the BST?

hard

A. [15, 10, 20, 25, 30, 35, 40]

B. [10, 15, 20, 25, 30, 35, 40]

C. [10, 20, 15, 25, 30, 35, 40]

D. [10, 15, 20, 30, 25, 35, 40]

Solution

1. Step 1: Insert 15 and 35 into BST

   Insert 15: less than 20, greater than 10, goes right of 10. Insert 35: less than 40, greater than 30, goes right of 30.

2. Step 2: Perform in-order traversal

   In-order traversal visits nodes in ascending order: left subtree, root, right subtree. The order is 10, 15, 20, 25, 30, 35, 40.

3. Final Answer:

   [10, 15, 20, 25, 30, 35, 40] -> Option B

4. Quick Check:

   In-order traversal = sorted nodes [OK]

Hint: In-order traversal of BST is sorted list [OK]

Common Mistakes:

• Placing 15 or 35 in wrong subtree
• Confusing traversal order
• Listing nodes unsorted in output