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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order? The BST is printed using in-order traversal (left -> root -> right).

DSA C++

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;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->data << " -> ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    inorder(root);
    std::cout << "null" << std::endl;
    return 0;
}

A 3 -> 5 -> 7 -> 10 -> 15 -> null

B 10 -> 5 -> 15 -> 3 -> 7 -> null

C 15 -> 10 -> 7 -> 5 -> 3 -> null

D 3 -> 7 -> 5 -> 10 -> 15 -> null

💡 Hint

Remember, in-order traversal prints nodes in ascending order for BST.

In-order traversal of a BST prints values in sorted order. After inserting 10, 5, 15, 3, 7, the sorted order is 3, 5, 7, 10, 15.

❓ Predict Output

intermediate

Output after inserting duplicate value in BST

What is the printed state of the BST after inserting the values 20, 10, 30, 20 in that order? Assume duplicates are inserted to the right subtree. The BST is printed using in-order traversal.

DSA C++

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;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->data << " -> ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 20);
    inorder(root);
    std::cout << "null" << std::endl;
    return 0;
}

A 10 -> 30 -> 20 -> 20 -> null

B 10 -> 20 -> 30 -> 20 -> null

C 20 -> 10 -> 30 -> 20 -> null

D 10 -> 20 -> 20 -> 30 -> null

💡 Hint

Duplicates go to the right subtree, so the second 20 is after the first 20.

In-order traversal prints nodes in ascending order including duplicates. The second 20 is inserted to the right of the first 20, so output is 10, 20, 20, 30.

🔧 Debug

advanced

Identify the error in BST insert function

What error will this BST insert function cause when inserting values? Explain the output or error.

DSA C++

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;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->data << " -> ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    // Print in-order
    inorder(root);
    std::cout << "null" << std::endl;
    return 0;
}

A Compilation error due to missing inorder function

B 5 -> 10 -> 10 -> 15 -> null

C 5 -> 10 -> 15 -> null

D Stack overflow due to infinite recursion

💡 Hint

Check how duplicates are handled in the insert function.

Duplicates are inserted to the left subtree because of <= condition. So both 10s appear in the tree. The in-order traversal prints 5, 10, 10, 15.

❓ Predict Output

advanced

Output after inserting nodes and printing pre-order traversal

What is the printed state of the BST after inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order? The BST is printed using pre-order traversal (root -> left -> right).

DSA C++

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;
}

void preorder(Node* root) {
    if (!root) return;
    std::cout << root->data << " -> ";
    preorder(root->left);
    preorder(root->right);
}

int main() {
    Node* root = nullptr;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int val : values) root = insert(root, val);
    preorder(root);
    std::cout << "null" << std::endl;
    return 0;
}

A 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14 -> null

B 8 -> 10 -> 14 -> 13 -> 3 -> 6 -> 7 -> 4 -> 1 -> null

C 8 -> 3 -> 1 -> 6 -> 4 -> 7 -> 10 -> 14 -> 13 -> null

D 3 -> 1 -> 6 -> 4 -> 7 -> 8 -> 10 -> 14 -> 13 -> null

💡 Hint

Pre-order prints root first, then left subtree, then right subtree.

Pre-order traversal visits nodes in root-left-right order. After inserting, the root is 8, left subtree starts with 3, right subtree with 10, etc.

🧠 Conceptual

expert

Number of nodes in BST after insertions

After inserting the values 50, 30, 70, 20, 40, 60, 80, 70, 30 into an empty BST (duplicates inserted to the right), how many nodes does the BST contain?

A 9

B 8

C 10

D 7

💡 Hint

Count unique values plus duplicates inserted as new nodes.

Values inserted: 50,30,70,20,40,60,80,70(duplicate),30(duplicate). Each duplicate is inserted as a new node to the right. So total nodes = 7 unique + 1 duplicate 70 + 1 duplicate 30 = 9 nodes.

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