BST Insert Operation in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST after inserting nodes

What is the printed in-order traversal of the BST after inserting the values 10, 5, 15, 3, 7 in that order?

DSA C#

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

class BST {
    public Node root;
    public void Insert(int val) {
        root = InsertRec(root, val);
    }
    private Node InsertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = InsertRec(root.left, val);
        else root.right = InsertRec(root.right, val);
        return root;
    }
    public void InOrder(Node node) {
        if (node == null) return;
        InOrder(node.left);
        System.Console.Write(node.val + " ");
        InOrder(node.right);
    }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Insert(3);
tree.Insert(7);
tree.InOrder(tree.root);

A 10 5 3 7 15

B 3 5 7 10 15

C 15 10 7 5 3

D 5 3 7 10 15

💡 Hint

In-order traversal of a BST prints values in sorted order.

In-order traversal visits left subtree, root, then right subtree. After inserting 10, 5, 15, 3, 7, the BST in-order traversal prints sorted values: 3 5 7 10 15.

❓ Predict Output

intermediate

BST structure after inserting nodes

After inserting 20, 10, 30, 25, 35 into an empty BST, what is the pre-order traversal output?

DSA C#

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

class BST {
    public Node root;
    public void Insert(int val) {
        root = InsertRec(root, val);
    }
    private Node InsertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = InsertRec(root.left, val);
        else root.right = InsertRec(root.right, val);
        return root;
    }
    public void PreOrder(Node node) {
        if (node == null) return;
        System.Console.Write(node.val + " ");
        PreOrder(node.left);
        PreOrder(node.right);
    }
}

var tree = new BST();
tree.Insert(20);
tree.Insert(10);
tree.Insert(30);
tree.Insert(25);
tree.Insert(35);
tree.PreOrder(tree.root);

A 30 20 10 25 35

B 10 20 25 30 35

C 20 30 10 25 35

D 20 10 30 25 35

💡 Hint

Pre-order traversal visits root, left subtree, then right subtree.

Pre-order traversal prints root first, then left subtree, then right subtree. After insertion, the root is 20, left child 10, right child 30 with children 25 and 35.

🔧 Debug

advanced

Identify the error in BST insert method

What error will this BST insert code cause when inserting duplicate values?

DSA C#

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

class BST {
    public Node root;
    public void Insert(int val) {
        root = InsertRec(root, val);
    }
    private Node InsertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = InsertRec(root.left, val);
        else if (val > root.val) root.right = InsertRec(root.right, val);
        return root;
    }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(10);

A NullReferenceException at InsertRec

B No error, duplicates are ignored

C StackOverflowException due to infinite recursion

D Compilation error due to missing else block

💡 Hint

Check what happens when val equals root.val in InsertRec.

The code does not handle the case when val equals root.val, so it neither inserts left nor right. This causes infinite recursion on the same node, leading to StackOverflowException.

🧠 Conceptual

advanced

BST Insert operation complexity

What is the worst-case time complexity of inserting a node into a BST with n nodes?

A O(n)

B O(log n)

C O(1)

D O(n log n)

💡 Hint

Consider the shape of the BST in the worst case.

In the worst case, the BST becomes a linked list (all nodes on one side). Inserting requires traversing all nodes, so time complexity is O(n).

🚀 Application

expert

Resulting BST after inserting sequence

Given an empty BST, after inserting the sequence 50, 30, 70, 20, 40, 60, 80, what is the post-order traversal output?

DSA C#

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

class BST {
    public Node root;
    public void Insert(int val) {
        root = InsertRec(root, val);
    }
    private Node InsertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = InsertRec(root.left, val);
        else root.right = InsertRec(root.right, val);
        return root;
    }
    public void PostOrder(Node node) {
        if (node == null) return;
        PostOrder(node.left);
        PostOrder(node.right);
        System.Console.Write(node.val + " ");
    }
}

var tree = new BST();
int[] values = {50, 30, 70, 20, 40, 60, 80};
foreach (var v in values) tree.Insert(v);
tree.PostOrder(tree.root);

A 20 40 30 60 80 70 50

B 80 70 60 50 40 30 20

C 20 30 40 50 60 70 80

D 50 30 20 40 70 60 80

💡 Hint

Post-order traversal visits left subtree, right subtree, then root.

Post-order traversal prints left subtree nodes first, then right subtree nodes, then the root. For the given insertions, the output is 20 40 30 60 80 70 50.

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