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?

No→Move to child node

Yes↓

Insert new node here

↓

Done

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

Execution Sample

DSA C#

class Node {
  public int data;
  public Node left, right;
  public Node(int val) {
    data = val;
    left = null;
    right = null;
  }
}

void Insert(ref Node root, int val) {
  Node newNode = new Node(val);
  if (root == null) {
    root = newNode;
    return;
  }
  Node current = root;
  Node parent = null;
  while (current != null) {
    parent = current;
    if (val < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  if (val < parent.data) {
    parent.left = newNode;
  } else {
    parent.right = newNode;
  }
}

This code inserts a value into a BST by comparing and moving left or right until insertion point is found.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Create new node with value 25	null	N/A	newNode = Node(25)	25 (new node)
2	Start at root	30	25 < 30	current = root(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:40│ │ data:50│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ └────────┘ └────────┘ └────────┘ root
3	Go left since 25 < 30	20	25 > 20	current = root.left (20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅ │ │ right:─┼──→ │ └────────┘ └────────┘ └────────┘ root
4	Go right since 25 > 20	null	null child found	right child of 20 = newNode(25)	BEFORE: ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:∅ │ │ right:─┼──→ │ └────────┘ └────────┘ └────────┘ root AFTER: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:25│ │ data:40│ │ left:──┼──→ │ left:∅ │ │ left:∅ │ │ left:∅ │ │ right:─┼──→ │ right:─┼──→ │ right:∅ │ │ right:─┼──→ │ └────────┘ └────────┘ └────────┘ └────────┘ root
5	Insertion complete	N/A	N/A	N/A	Final BST with 25 inserted

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we move left or right based on comparison?

Because BST property requires left child < node and right child ≥ node. See execution_table steps 2 and 3 where comparisons decide direction.

Why do we insert at the null child instead of replacing a node?

We insert at null child to keep existing nodes intact and maintain BST structure. Step 4 shows insertion at null right child of 20.

What happens if the tree is empty?

If root is null, new node becomes root. Here root was not null, so we started at root (step 2).

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 25

C Node with value 20

D null

💡 Hint

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

At which step does the insertion actually happen?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look for 'Pointer Changes' and 'Visual State' showing newNode linked in execution_table.

If the new value was 35 instead of 25, which direction would we go from root at step 2?

A Go right

B Insert at root

C Go left

D Stop

💡 Hint

Compare new value with root value in execution_table step 2.

Concept Snapshot

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

Full Transcript

This visual trace shows how to insert a value into a Binary Search Tree (BST). We create a new node, start at the root, and compare the new value with current nodes. If the new value is smaller, we move left; if larger or equal, we move right. We continue until we find a null child pointer, where we insert the new node. The pointer changes and tree structure update are shown step-by-step. This keeps the BST property intact.

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 add a new node while keeping the BST property intact

C. To find the maximum value in the BST

D. To balance the BST automatically

Solution

1. Step 1: Understand the Insert operation

   The Insert operation adds a new value to the BST while maintaining the order property: left child < parent < right child.

2. Step 2: Identify the purpose of Insert

   Insert does not delete nodes, find max, or balance the tree automatically. Its main job is to add nodes correctly.

3. Final Answer:

   To add a new node while keeping the BST property intact -> Option B

4. Quick Check:

   Insert = Add node correctly [OK]

Hint: Insert adds nodes preserving 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 C# method signature for inserting a value into a BST node class?

easy

A. public void Insert(int value)

B. void InsertNode(int value, Node root)

C. private Node Insert(int value, Node root)

D. public int Insert(int value)

Solution

1. Step 1: Understand typical Insert method signature

   Insert usually returns the updated root node after insertion, so return type is Node, and it takes the root and value as parameters.

2. Step 2: Check method access and parameters

   Private method with signature Node Insert(int value, Node root) fits common recursive insert pattern.

3. Final Answer:

   private Node Insert(int value, Node root) -> Option C

4. Quick Check:

   Insert returns updated node [OK]

Hint: Insert returns updated root node [OK]

Common Mistakes:

• Using void return type for recursive insert
• Incorrect parameter order or missing root node
• Making Insert public when it should be private helper

3. What will be the in-order traversal output after inserting 15 into this BST?

      10
     /  \
    5    20
         /
        17

Insert operation: Insert(15)

medium

A. 5 -> 10 -> 15 -> 17 -> 20 -> null

B. 5 -> 10 -> 17 -> 15 -> 20 -> null

C. 5 -> 10 -> 15 -> 20 -> 17 -> null

D. 5 -> 10 -> 20 -> 17 -> 15 -> null

Solution

1. Step 1: Insert 15 into BST

   Starting at root 10, 15 > 10, go right to 20. 15 < 20, go left to 17. 15 < 17, insert as left child of 17.

2. Step 2: Perform in-order traversal

   In-order visits left, root, right: 5, 10, 15, 17, 20.

3. Final Answer:

   5 -> 10 -> 15 -> 17 -> 20 -> null -> Option A

4. Quick Check:

   In-order sorted = 5,10,15,17,20 [OK]

Hint: Insert left if smaller, right if larger, then in-order sorts [OK]

Common Mistakes:

• Inserting 15 as right child of 17
• Misordering nodes in traversal
• Ignoring BST property during insertion

4. Given this Insert method snippet, what is the error?

private Node Insert(int value, Node root) {
  if (root == null) {
    root = new Node(value);
  } else if (value < root.Value) {
    Insert(value, root.Left);
  } else {
    Insert(value, root.Right);
  }
  return root;
}

medium

A. Missing assignment when inserting into left or right subtree

B. Incorrect base case for null root

C. Method should return void instead of Node

D. Using else instead of else if for right subtree insertion

Solution

1. Step 1: Analyze recursive calls

   Recursive calls to Insert on left or right subtree do not assign the returned node back to root.Left or root.Right.

2. Step 2: Identify fix

   Must assign: root.Left = Insert(value, root.Left); and similarly for right to update tree links.

3. Final Answer:

   Missing assignment when inserting into left or right subtree -> Option A

4. Quick Check:

   Assign recursive result to subtree [OK]

Hint: Always assign recursive insert result to child node [OK]

Common Mistakes:

• Not assigning recursive insert result
• Changing base case incorrectly
• Confusing return type with void

5. You have a BST with nodes 10, 5, 15. You want to insert 12 and 18. After insertion, which of the following represents the correct pre-order traversal?

hard

A. 10 -> 15 -> 18 -> 12 -> 5 -> null

B. 10 -> 5 -> 12 -> 15 -> 18 -> null

C. 10 -> 15 -> 5 -> 12 -> 18 -> null

D. 10 -> 5 -> 15 -> 12 -> 18 -> null

Solution

1. Step 1: Insert 12 and 18 into BST

   Start with root 10, left child 5, right child 15. Insert 12: 12 < 15, goes left of 15. Insert 18: 18 > 15, goes right of 15.

2. Step 2: Perform pre-order traversal

   Pre-order visits root, left, right: 10, 5, 15, 12, 18.

3. Final Answer:

   10 -> 5 -> 15 -> 12 -> 18 -> null -> Option D

4. Quick Check:

   Pre-order = root-left-right [OK]

Hint: Pre-order: root first, then left, then right [OK]

Common Mistakes:

• Mixing pre-order with in-order or post-order
• Inserting nodes in wrong subtree
• Misplacing 12 and 18 in traversal