BST Insert Operation in DSA C - Build from Scratch

BST Insert Operation

📖 Scenario: You are building a simple phone book application that stores phone numbers in a Binary Search Tree (BST) to keep them sorted for quick search and insertion.

🎯 Goal: Build a program that inserts phone numbers into a BST and prints the tree in sorted order.

📋 What You'll Learn

Create a BST node structure with integer phone number data

Write a function to insert a new phone number into the BST

Write a function to print the BST in ascending order (inorder traversal)

Insert given phone numbers into the BST and print the sorted phone numbers

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases use BSTs to keep data sorted for fast searching and insertion.

💼 Career

Understanding BST insertions is fundamental for software engineers working with data structures, databases, and performance optimization.

1

Create BST Node Structure

Create a struct Node with an int data field, and two pointers left and right to struct Node.

DSA C

# Define the struct Node with int data and left, right pointers
// Your code here

Hint

Think of each node as a box holding a number and two arrows pointing to left and right child nodes.

2

Create Insert Function

Write a function struct Node* insert(struct Node* root, int data) that inserts data into the BST rooted at root and returns the new root. Use recursion and create a new node when root is NULL.

DSA C

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Write insert function here
// Your code here

Hint

Insert smaller numbers to the left, bigger or equal to the right. Create a new node when you reach a NULL spot.

3

Create Inorder Print Function

Write a function void inorder(struct Node* root) that prints the BST nodes in ascending order using inorder traversal. Print each data followed by a space.

DSA C

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

#include 
#include 

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

// Write inorder function here
// Your code here

Hint

Visit left child, print current node, then visit right child recursively.

4

Insert Data and Print BST

In main(), create a struct Node* root initialized to NULL. Insert these phone numbers in order: 50, 30, 70, 20, 40, 60, 80 using the insert function. Then call inorder(root) to print the sorted phone numbers.

DSA C

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

#include 
#include 

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

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

int main() {
    struct Node* root = NULL;
    // Insert phone numbers here
    // Your code here
    // Print the BST in sorted order
    // Your code here
    return 0;
}

Hint

Insert each number by calling insert and update root. Then call inorder(root) to print.

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