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;
    struct Node* left;
    struct Node* right;
};

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d -> ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    inorder(root);
    printf("null\n");
    return 0;
}

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

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

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

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

💡 Hint

Remember that in-order traversal of a BST prints values in ascending order.

In-order traversal visits nodes in left-root-right order. After inserting 10, 5, 15, 3, 7, the BST structure is: 10 / \ 5 15 / \ 3 7 So the in-order traversal prints: 3 -> 5 -> 7 -> 10 -> 15 -> null.

❓ Predict Output

intermediate

BST structure after inserting duplicate value

What is the in-order traversal output after inserting the values 20, 10, 30, 20 into an empty BST? Assume duplicates are inserted to the right subtree.

DSA C

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// In-order traversal same as before

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

B 10 -> 20 -> 30 -> null

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

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

💡 Hint

Duplicates go to the right subtree, so the second 20 is placed as right child of the first 20.

The BST after insertions: 20 / \ 10 30 \ 20 In-order traversal visits left-root-right, so output is 10 -> 20 -> 20 -> 30 -> null.

🔧 Debug

advanced

Identify the error in BST insert function

What error will occur when running this BST insert function code snippet?

DSA C

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (val <= root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// main calls insert with root = NULL and val = 5

A Stack overflow due to infinite recursion

B Memory leak due to missing free() calls

C Segmentation fault due to uninitialized pointer

D No error, code runs correctly

💡 Hint

Check base case and recursive calls carefully.

The insert function correctly handles the base case when root is NULL by allocating a new node. Recursive calls correctly update left or right child pointers. No infinite recursion or uninitialized pointers occur. So the code runs correctly.

❓ Predict Output

advanced

BST structure after inserting negative and positive values

What is the in-order traversal output after inserting the values 0, -10, 10, -20, 20 into an empty BST?

DSA C

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// In-order traversal same as before

A -10 -> -20 -> 0 -> 10 -> 20 -> null

B -20 -> -10 -> 0 -> 10 -> 20 -> null

C 0 -> -10 -> -20 -> 10 -> 20 -> null

D -20 -> 0 -> -10 -> 10 -> 20 -> null

💡 Hint

In-order traversal prints values in ascending order.

The BST structure after insertions: 0 / \ -10 10 / \ -20 20 In-order traversal visits nodes in ascending order: -20 -> -10 -> 0 -> 10 -> 20 -> null.

🧠 Conceptual

expert

Number of nodes in BST after insertions

If you insert the values 8, 3, 10, 1, 6, 14, 4, 7, 13 into an empty BST, how many nodes will the BST contain?

A 9

B 7

C 10

D 8

💡 Hint

Each insertion adds one node since no duplicates are inserted.

All inserted values are unique. Each insertion adds one node. Total nodes = number of inserted values = 9.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To find the height of the BST

B. To delete a node from the BST

C. To add a new node while keeping the BST property intact

D. To traverse the BST in order

Solution

1. Step 1: Understand BST property

   A BST keeps nodes ordered so that left child is smaller and right child is larger than the parent.

2. Step 2: Purpose of insert operation

   Insert adds a new node in the correct position to maintain this order.

3. Final Answer:

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

4. Quick Check:

   Insert = Add node correctly [OK]

Hint: Insert means add node keeping order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert changes tree traversal
• Assuming insert changes tree height always

2. Which of the following is the correct way to declare a BST node structure in C for insertion?

easy

A. typedef struct Node { int data; struct Node* left; struct Node* right; } Node;

B. struct Node { int data; int left; int right; };

C. typedef struct Node { int data; Node left; Node right; } Node;

D. struct Node { int data; struct Node left; struct Node right; };

Solution

1. Step 1: Check pointer usage in struct

   BST nodes must have pointers to left and right child nodes, not direct structs or ints.

2. Step 2: Validate correct syntax

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; uses pointers to struct Node correctly, others use wrong types or missing pointers.

3. Final Answer:

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; -> Option A

4. Quick Check:

   Node pointers needed for children [OK]

Hint: Use pointers for left and right child nodes [OK]

Common Mistakes:

• Using int instead of pointers for children
• Missing struct keyword before Node*
• Declaring children as struct instead of pointers

3. Given the following BST and insertion code snippet, what will be the inorder traversal output after inserting 25?

    20
   /  \
 10   30

// Insert function called with root and 25

medium

A. [10, 20, 25, 30]

B. [10, 20, 30, 25]

C. [10, 25, 20, 30]

D. [20, 10, 25, 30]

Solution

1. Step 1: Insert 25 in BST

   25 is greater than 20, so move right to 30. 25 is less than 30, so insert as left child of 30.

2. Step 2: Inorder traversal after insertion

   Inorder visits left, root, right: 10, 20, 25, 30.

3. Final Answer:

   [10, 20, 25, 30] -> Option A

4. Quick Check:

   Inorder sorted = [10, 20, 25, 30] [OK]

Hint: Inorder traversal of BST is sorted list [OK]

Common Mistakes:

• Inserting 25 as right child of 30
• Misordering inorder traversal
• Confusing preorder with inorder

4. Identify the error in the following BST insert function snippet:

Node* insert(Node* root, int val) {
  if (root == NULL) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
  }
  if (val < root->data) {
    root->left = insert(root->left, val);
  } else {
    root->right = insert(root->right, val);
  }
  return root;
}

medium

A. Incorrect comparison operator for val and root->data

B. Missing return statement after creating new node

C. Using malloc instead of calloc

D. Not freeing memory of old nodes

Solution

1. Step 1: Check base case return

   When root is NULL, new node is created but not returned, so function returns garbage.

2. Step 2: Fix missing return

   Must return newNode immediately after creation to link it properly.

3. Final Answer:

   Missing return statement after creating new node -> Option B

4. Quick Check:

   Return new node in base case [OK]

Hint: Always return new node after malloc in base case [OK]

Common Mistakes:

• Forgetting to return new node in base case
• Incorrect pointer assignments
• Ignoring memory allocation errors

5. You have a BST with nodes 15, 10, 20, 8, 12, 17, 25. You want to insert 16. After insertion, what is the preorder traversal of the BST?

hard

A. [15, 10, 8, 12, 20, 17, 25, 16]

B. [15, 10, 8, 12, 20, 16, 17, 25]

C. [15, 10, 8, 12, 20, 25, 17, 16]

D. [15, 10, 8, 12, 20, 17, 16, 25]

Solution

1. Step 1: Insert 16 in BST

   16 is less than 17, so it becomes left child of 17.

2. Step 2: Preorder traversal after insertion

   Preorder visits root, left, right: 15, 10, 8, 12, 20, 17, 16, 25.

3. Final Answer:

   [15, 10, 8, 12, 20, 17, 16, 25] -> Option D

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left subtree, then right subtree [OK]

Common Mistakes:

• Inserting 16 as right child of 17
• Mixing preorder with inorder or postorder
• Skipping the new node in traversal