BST Insert Operation in DSA C - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value in a Binary Search Tree (BST) changes as the tree grows.

How does the number of steps needed to insert depend on the tree size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 = newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}
    

This code inserts a value into a BST by recursively finding the correct spot and adding a new node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down the tree nodes.
• How many times: At most once per tree level until the correct leaf spot is found.

How Execution Grows With Input

Each insert moves down one path from root to leaf, checking nodes along the way.

Input Size (n)	Approx. Operations
10	Up to 4-5 steps (tree height)
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: In a balanced tree, steps grow slowly, roughly proportional to the tree height, not total nodes.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the time depends on how tall the tree is, which can be much smaller than total nodes if balanced.

Common Mistake

[X] Wrong: "Insertion always takes time proportional to the number of nodes (n)."

[OK] Correct: In a balanced BST, insertion only follows one path down, so it depends on height, not total nodes.

Interview Connect

Understanding BST insert time helps you explain how data structures keep operations efficient as data grows.

Self-Check

"What if the BST becomes a linked list (completely unbalanced)? How would the time complexity change?"

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