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.