BST Insert Operation in DSA C

Mental Model

A binary search tree keeps smaller values on the left and bigger values on the right. To insert, we find the right spot by comparing values and add the new node there.

Analogy: Imagine a sorted family tree where each child is placed left if younger and right if older. To add a new family member, you walk down the tree comparing ages until you find the empty spot.

    10
   /  \
  5    15
 / \   / \
null null null null

Dry Run Walkthrough

Input: Insert value 12 into BST: 10 -> 5 -> 15

Goal: Add 12 to the BST while keeping the order property

Step 1: Compare 12 with root 10, move right because 12 > 10

10 -> [curr->15]
5 null null null

Why: We go right since 12 is bigger than 10

Step 2: Compare 12 with 15, move left because 12 < 15

10 -> 15 -> [curr->null]
5 null null null

Why: We go left since 12 is smaller than 15

Step 3: Insert 12 as left child of 15

    10
   /  \
  5    15
       / \
     12  null

Why: Found empty spot to insert 12

Result:

    10 -> 5 -> 15
           / \
         12  null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for BST
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert function for BST
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return newNode(data); // insert at empty spot
    }
    if (data < root->data) {
        root->left = insert(root->left, data); // go left
    } else if (data > root->data) {
        root->right = insert(root->right, data); // go right
    }
    return root; // unchanged root
}

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

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

if (root == NULL) { return newNode(data); }

insert new node when empty spot found

if (data < root->data) { root->left = insert(root->left, data); }

go left if data smaller than current node

else if (data > root->data) { root->right = insert(root->right, data); }

go right if data bigger than current node

return root;

return unchanged root after insertion

Output

5 10 12 15 

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down to insert

Space: O(h) due to recursion stack for the path from root to insertion point

vs Alternative: Compared to inserting in an unsorted tree (O(1)), BST insert is slower but keeps data ordered for fast search

Edge Cases

Empty tree

New node becomes root

DSA C

if (root == NULL) { return newNode(data); }

Insert duplicate value

Duplicate ignored, tree unchanged

DSA C

else if (data > root->data) { ... } // no insertion if equal

Insert smallest or largest value

Inserted at leftmost or rightmost leaf

DSA C

recursive calls to left or right child

When to Use This Pattern

When you need to keep data sorted with fast search and insert, use BST insert to place new values in order.

Common Mistakes

Mistake: Not returning the updated child pointer after recursive insert
Fix: Always assign the recursive call result back to root->left or root->right

Summary

Inserts a new value into the binary search tree while keeping it ordered.

Use when you want to add data to a BST and maintain sorted order for fast lookup.

The key is to find the empty spot by comparing values and insert there recursively.

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