BST Insert Operation in DSA C#

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right. To insert, we find the right spot by comparing values step-by-step.

Analogy: Imagine placing books on a shelf where each book must go to the left if it's lighter or to the right if it's heavier, so the shelf stays sorted.

    10
   /  \
  5    15
 / \   / \
null null null null

Dry Run Walkthrough

Input: Insert value 12 into BST: 10 -> 5 -> 15

Goal: Add 12 in the correct position to keep BST rules

Step 1: Compare 12 with root 10, 12 is greater, go right

10 -> 5 -> [curr->15]
Left and right children of 15 are null

Why: We move right because 12 is bigger than 10

Step 2: Compare 12 with 15, 12 is smaller, go left

10 -> 5 -> 15 -> [curr->null]

Why: We move left because 12 is less than 15

Step 3: Insert 12 as left child of 15

    10
   /  \
  5    15
      /  \
    12   null

Why: Found empty spot on left of 15 to insert 12

Result:

    10
   /  \
  5    15
      /  \
    12   null

Annotated Code

DSA C#

using System;

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BST
{
    public Node Root;

    public BST()
    {
        Root = null;
    }

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
            return new Node(value); // create new node when spot found

        if (value < root.Value)
            root.Left = InsertRec(root.Left, value); // go left if smaller
        else if (value > root.Value)
            root.Right = InsertRec(root.Right, value); // go right if bigger
        // if value == root.Value, do nothing (no duplicates)

        return root; // return unchanged root pointer
    }

    public void PrintInOrder()
    {
        PrintInOrderRec(Root);
        Console.WriteLine();
    }

    private void PrintInOrderRec(Node root)
    {
        if (root == null) return;
        PrintInOrderRec(root.Left);
        Console.Write(root.Value + " ");
        PrintInOrderRec(root.Right);
    }
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        tree.Insert(10);
        tree.Insert(5);
        tree.Insert(15);
        tree.Insert(12);
        tree.PrintInOrder();
    }
}

if (root == null) return new Node(value);

create new node when empty spot found

if (value < root.Value) root.Left = InsertRec(root.Left, value);

go left if value is smaller than current node

else if (value > root.Value) root.Right = InsertRec(root.Right, value);

go right if value is bigger than current node

return root;

return current node to link back after insertion

Output

5 10 12 15 

Complexity Analysis

Time: O(h) where h is tree height, because we follow one path down to insert

Space: O(h) due to recursion stack in worst case of unbalanced tree

vs Alternative: Compared to array insert O(n) shifting, BST insert is faster on average O(log n) if balanced

Edge Cases

Insert into empty tree

New node becomes root

DSA C#

if (root == null)
    return new Node(value);

Insert duplicate value

No insertion happens, tree stays same

DSA C#

else if (value > root.Value)
    root.Right = InsertRec(root.Right, value);

Insert smallest or largest value

Node added as leftmost or rightmost leaf

DSA C#

if (value < root.Value)
    root.Left = InsertRec(root.Left, value);

When to Use This Pattern

When you need to add values to a sorted tree structure and keep order, use BST insert to place new values by comparing step-by-step.

Common Mistakes

Mistake: Not updating the parent's left or right pointer after recursive insert
Fix: Assign the recursive call result back to root.Left or root.Right to link new node

Mistake: Inserting duplicates without check, causing duplicates in BST
Fix: Add condition to ignore insertion if value equals current node's value

Summary

Inserts a new value into the binary search tree while keeping it sorted.

Use when you want to add data to a BST and maintain its order property.

The key is to compare and move left or right until finding an empty spot to insert.

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