BST Insert Operation in DSA C - Execution Trace

Concept Flow - BST Insert Operation

Create new node with value

↓

Is tree empty?

Yes→Set new node as root

No↓

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

This flow shows how to insert a new value into a BST by comparing and moving left or right until the correct empty spot is found.

Execution Sample

DSA C

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

void insert(struct Node** root, int val);

This code defines a BST node and a function to insert a value into the BST.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Create new node with value 25	∅	new_node = Node(25)	∅
2	Check if root is null	root = ∅	root = new_node	┌────────┐ │ data:25│ │ left:∅ │ │ right:∅│ └────────┘ root
3	Insert complete	root = 25	No change	┌────────┐ │ data:25│ │ left:∅ │ │ right:∅│ └────────┘ root
4	Create new node with value 15	root = 25	new_node = Node(15)	┌────────┐ │ data:25│ │ left:∅ │ │ right:∅│ └────────┘ root
5	Compare 15 with 25 (current root)	current = 25	Move left since 15 < 25	┌────────┐ ∅ │ data:25│──→ ∅ │ left:∅ │ │ right:∅│ └────────┘ root
6	Left child is null, insert new node here	current = 25	current.left = new_node(15)	┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ left:──┼ │ left:∅ │ │ right:∅│ │ right:∅│ └────────┘ └────────┘ root left child
7	Insert complete	root = 25	No change	┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ left:──┼ │ left:∅ │ │ right:∅│ │ right:∅│ └────────┘ └────────┘ root left child
8	Create new node with value 35	root = 25	new_node = Node(35)	┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ left:──┼ │ left:∅ │ │ right:∅│ │ right:∅│ └────────┘ └────────┘ root left child
9	Compare 35 with 25 (current root)	current = 25	Move right since 35 > 25	┌────────┐ ∅ │ data:25│──→ ∅ │ left:──┼ │ right:∅│ └────────┘ root
10	Right child is null, insert new node here	current = 25	current.right = new_node(35)	┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ root left child right child
11	Insert complete	root = 25	No change	┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ root left child right child
12	Create new node with value 20	root = 25	new_node = Node(20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ root left child right child
13	Compare 20 with 25 (root)	current = 25	Move left since 20 < 25	┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ root left child right child
14	Compare 20 with 15 (left child)	current = 15	Move right since 20 > 15	┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ right:∅│──→ ∅ │ right:∅│ └────────┘ └────────┘ └────────┘ root left child right child
15	Right child of 15 is null, insert new node here	current = 15	current.right = new_node(20)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ data:20│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ └────────┘ root left child right child right child of 15
16	Insert complete	root = 25	No change	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:25│──→ │ data:15│ │ data:35│ │ data:20│ │ left:──┼ │ left:∅ │ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅│ │ right:∅│ │ right:∅│ └────────┘ └────────┘ └────────┘ └────────┘ root left child right child right child of 15

💡 Insertion stops when the new node is linked as a null child of a leaf node.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	After Step 12	Final
root	∅	Node(25)	Node(25)	Node(25)	Node(25)	Node(25)
new_node	∅	Node(25)	Node(15)	Node(35)	Node(20)	Node(20)
current	∅	Node(25)	Node(25)	Node(25)	Node(15)	Node(15)

Key Moments - 3 Insights

Why do we check if the left or right child is null before inserting?

Because the new node must be inserted at a position where the child pointer is null, as shown in execution_table rows 6, 10, and 15 where insertion happens only when the child is null.

Why do we move left if the new value is smaller and right if greater or equal?

This maintains the BST property. The execution_table rows 5 and 9 show moving left or right based on comparison to keep the tree ordered.

What happens if the tree is empty at the start?

The new node becomes the root, as shown in execution_table row 2 where root was null and is set to the new node.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what pointer change happens?

A current.left points to new node with value 15

B current.right points to new node with value 15

C root points to new node with value 15

D No pointer change

💡 Hint

Check the 'Pointer Changes' column at step 6 in execution_table.

At which step does the new node with value 35 get inserted?

A Step 9

B Step 10

C Step 11

D Step 8

💡 Hint

Look for the step where 'current.right = new_node(35)' happens in execution_table.

If we insert a value smaller than 15, how would the visual state change after insertion?

A A new node would be added as right child of 25

B A new node would be added as right child of 15

C A new node would be added as left child of 15

D No change in the tree

💡 Hint

Refer to the pattern of insertion shown in execution_table steps 5-6 and 14-15.

Concept Snapshot

BST Insert Operation:
- Create new node
- If tree empty, set root = new node
- Else start at root
- Compare new value with current node
- Move left if smaller, right if greater or equal
- Repeat until null child found
- Insert new node there
- Maintains BST order property

Full Transcript

The BST insert operation starts by creating a new node with the value to insert. If the tree is empty, this new node becomes the root. Otherwise, starting from the root, we compare the new value with the current node's value. If the new value is smaller, 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, where we insert the new node. This process maintains the binary search tree property where left children are smaller and right children are greater or equal. The execution steps show pointer changes and the tree's visual state after each insertion.

Practice

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

easy

A. To find the height of the BST

B. To delete a node from the BST

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

D. To traverse the BST in order

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 C

4. Quick Check:

   Insert = Add node correctly [OK]

Hint: Insert means add node keeping order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert changes tree traversal
• Assuming insert changes tree height always

2. Which of the following is the correct way to declare a BST node structure in C for insertion?

easy

A. typedef struct Node { int data; struct Node* left; struct Node* right; } Node;

B. struct Node { int data; int left; int right; };

C. typedef struct Node { int data; Node left; Node right; } Node;

D. struct Node { int data; struct Node left; struct Node right; };

Solution

1. Step 1: Check pointer usage in struct

   BST nodes must have pointers to left and right child nodes, not direct structs or ints.

2. Step 2: Validate correct syntax

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; uses pointers to struct Node correctly, others use wrong types or missing pointers.

3. Final Answer:

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; -> Option A

4. Quick Check:

   Node pointers needed for children [OK]

Hint: Use pointers for left and right child nodes [OK]

Common Mistakes:

• Using int instead of pointers for children
• Missing struct keyword before Node*
• Declaring children as struct instead of pointers

3. Given the following BST and insertion code snippet, what will be the inorder traversal output after inserting 25?

    20
   /  \
 10   30

// Insert function called with root and 25

medium

A. [10, 20, 25, 30]

B. [10, 20, 30, 25]

C. [10, 25, 20, 30]

D. [20, 10, 25, 30]

Solution

1. Step 1: Insert 25 in BST

   25 is greater than 20, so move right to 30. 25 is less than 30, so insert as left child of 30.

2. Step 2: Inorder traversal after insertion

   Inorder visits left, root, right: 10, 20, 25, 30.

3. Final Answer:

   [10, 20, 25, 30] -> Option A

4. Quick Check:

   Inorder sorted = [10, 20, 25, 30] [OK]

Hint: Inorder traversal of BST is sorted list [OK]

Common Mistakes:

• Inserting 25 as right child of 30
• Misordering inorder traversal
• Confusing preorder with inorder

4. Identify the error in the following BST insert function snippet:

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

medium

A. Incorrect comparison operator for val and root->data

B. Missing return statement after creating new node

C. Using malloc instead of calloc

D. Not freeing memory of old nodes

Solution

1. Step 1: Check base case return

   When root is NULL, new node is created but not returned, so function returns garbage.

2. Step 2: Fix missing return

   Must return newNode immediately after creation to link it properly.

3. Final Answer:

   Missing return statement after creating new node -> Option B

4. Quick Check:

   Return new node in base case [OK]

Hint: Always return new node after malloc in base case [OK]

Common Mistakes:

• Forgetting to return new node in base case
• Incorrect pointer assignments
• Ignoring memory allocation errors

5. You have a BST with nodes 15, 10, 20, 8, 12, 17, 25. You want to insert 16. After insertion, what is the preorder traversal of the BST?

hard

A. [15, 10, 8, 12, 20, 17, 25, 16]

B. [15, 10, 8, 12, 20, 16, 17, 25]

C. [15, 10, 8, 12, 20, 25, 17, 16]

D. [15, 10, 8, 12, 20, 17, 16, 25]

Solution

1. Step 1: Insert 16 in BST

   16 is less than 17, so it becomes left child of 17.

2. Step 2: Preorder traversal after insertion

   Preorder visits root, left, right: 15, 10, 8, 12, 20, 17, 16, 25.

3. Final Answer:

   [15, 10, 8, 12, 20, 17, 16, 25] -> Option D

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left subtree, then right subtree [OK]

Common Mistakes:

• Inserting 16 as right child of 17
• Mixing preorder with inorder or postorder
• Skipping the new node in traversal