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 the numbers sorted for quick search and insertion.

🎯 Goal: Build a BST that can insert phone numbers one by one and then print the tree in sorted order (in-order traversal).

📋 What You'll Learn

Create a BST node structure with integer phone number data and left/right pointers

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

Insert given phone numbers into the BST

Print the BST in sorted order using in-order traversal

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding BST insertions is fundamental for software engineers working on data storage, search engines, and real-time applications.

1

Create BST Node Structure

Create a struct called Node with an int data field, and two pointers Node* left and Node* right initialized to nullptr. Then create a pointer root of type Node* and set it to nullptr.

DSA C++

// Define the Node struct and create root pointer
// Your code here

Hint

Think of Node as a box holding a number and two pointers to other boxes.

2

Create Insert Function

Write a function called insert that takes a Node*& root and an int value. If root is nullptr, create a new Node with value and assign it to root. Otherwise, if value is less than root->data, recursively call insert on root->left. Else, recursively call insert on root->right.

DSA C++

#include 

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

Node* root = nullptr;

// Write insert function here
// Your code here

Hint

Use recursion to find the correct place to insert the new number.

3

Insert Phone Numbers into BST

Use the insert function to insert these phone numbers into the BST in this order: 5551234, 5555678, 5550000, 5559999, 5551111.

DSA C++

#include 

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

Node* root = nullptr;

void insert(Node*& root, int value) {
    if (root == nullptr) {
        root = new Node{value, nullptr, nullptr};
        return;
    }
    if (value data) {
        insert(root->left, value);
    } else {
        insert(root->right, value);
    }
}

// Insert the phone numbers below
// Your code here

Hint

Call insert five times with the given numbers.

4

Print BST In-Order

Write a function called inOrder that takes a Node* root and prints the data of each node in ascending order separated by spaces. Then call inOrder(root) inside main after all insertions.

DSA C++

#include 

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

Node* root = nullptr;

void insert(Node*& root, int value) {
    if (root == nullptr) {
        root = new Node{value, nullptr, nullptr};
        return;
    }
    if (value data) {
        insert(root->left, value);
    } else {
        insert(root->right, value);
    }
}

void inOrder(Node* root) {
    // Your code here
}

int main() {
    insert(root, 5551234);
    insert(root, 5555678);
    insert(root, 5550000);
    insert(root, 5559999);
    insert(root, 5551111);

    // Call inOrder here
    // Your code here

    return 0;
}

Hint

Use recursion to print left subtree, current node, then right subtree.

Practice

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

easy

A. To delete a node from the BST

B. To find the height of the BST

C. To add a new node while maintaining BST properties

D. To traverse the BST in order

Solution

1. Step 1: Understand BST insert operation

   The insert operation adds a new node to the BST while keeping the order property intact: left child < parent < right child.

2. Step 2: Differentiate from other operations

   Deleting nodes, finding height, or traversing are different operations and do not describe insertion.

3. Final Answer:

   To add a new node while maintaining BST properties -> Option C

4. Quick Check:

   Insert = Add node maintaining order [OK]

Hint: Insert means add node keeping BST order intact [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert changes tree height only
• Mixing insert with traversal methods

2. Which of the following is the correct syntax to insert a value val into a BST using a recursive function in C++?

easy

A. root = insert(root, val);

B. insert(root, val);

C. root.insert(val);

D. insert(val, root);

Solution

1. Step 1: Understand recursive insert signature

   Recursive insert usually returns the new root after insertion, so assignment like root = insert(root, val); is needed.

2. Step 2: Check other options

   Calling insert(root, val); without assignment ignores updated root. root.insert(val); assumes method on node object which is uncommon. insert(val, root); has wrong parameter order.

3. Final Answer:

   root = insert(root, val); -> Option A

4. Quick Check:

   Assign returned root after insert [OK]

Hint: Assign root = insert(root, val) for recursive insertion [OK]

Common Mistakes:

• Not assigning the returned root after insertion
• Using wrong parameter order in insert call
• Assuming insert is a method of node object

3. Consider the following C++ code inserting values into an empty BST:

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;
}

int main() {
  Node* root = nullptr;
  root = insert(root, 10);
  root = insert(root, 5);
  root = insert(root, 15);
  root = insert(root, 12);
  return 0;
}

What is the structure of the BST after these insertions?

medium

A. 10 -> 5 -> 12 (left), 10 -> 15 -> null (right subtree)

B. 10 -> 15 -> null (left), 10 -> 5 -> 12 (right subtree)

C. 10 -> 12 -> 5 (left), 10 -> 15 -> null (right subtree)

D. 10 -> 5 -> null (left), 10 -> 15 -> 12 (right subtree)

Solution

1. Step 1: Insert 10, 5, 15, 12 step-by-step

   Start with empty root. Insert 10 as root. Insert 5 goes left of 10. Insert 15 goes right of 10. Insert 12 goes left of 15.

2. Step 2: Visualize BST structure

   Root 10 has left child 5 (no children), right child 15 with left child 12 (no right child).

3. Final Answer:

   10 -> 5 -> null (left), 10 -> 15 -> 12 (right subtree) -> Option D

4. Quick Check:

   Insert order builds left 5, right 15 with left 12 [OK]

Hint: Insert smaller left, larger right; 12 is left child of 15 [OK]

Common Mistakes:

• Placing 12 as right child of 15 instead of left
• Swapping left and right children of 10
• Ignoring null children in output

4. The following code attempts to insert a value into a BST but causes a runtime error:

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

What is the error and how to fix it?

medium

A. Missing return after creating new node; add return newNode;

B. Incorrect comparison operator; use <= instead of <

C. Should not assign to root->left or root->right

D. Node constructor is missing initialization

Solution

1. Step 1: Identify missing return in base case

   When root is nullptr, new node is created but not returned, so function continues and dereferences nullptr causing runtime error.

2. Step 2: Fix by returning new node immediately

   Add return newNode; inside the if block to return the newly created node and stop further execution.

3. Final Answer:

   Missing return after creating new node; add return newNode; -> Option A

4. Quick Check:

   Return new node on nullptr base case [OK]

Hint: Always return new node immediately when root is nullptr [OK]

Common Mistakes:

• Not returning new node causes nullptr dereference
• Changing comparison operator unnecessarily
• Misunderstanding pointer assignments

5. You have a BST with nodes 20, 10, 30, 25, 40. You want to insert 15 and 35. After insertion, which of the following is the correct in-order traversal of the BST?

hard

A. [15, 10, 20, 25, 30, 35, 40]

B. [10, 15, 20, 25, 30, 35, 40]

C. [10, 20, 15, 25, 30, 35, 40]

D. [10, 15, 20, 30, 25, 35, 40]

Solution

1. Step 1: Insert 15 and 35 into BST

   Insert 15: less than 20, greater than 10, goes right of 10. Insert 35: less than 40, greater than 30, goes right of 30.

2. Step 2: Perform in-order traversal

   In-order traversal visits nodes in ascending order: left subtree, root, right subtree. The order is 10, 15, 20, 25, 30, 35, 40.

3. Final Answer:

   [10, 15, 20, 25, 30, 35, 40] -> Option B

4. Quick Check:

   In-order traversal = sorted nodes [OK]

Hint: In-order traversal of BST is sorted list [OK]

Common Mistakes:

• Placing 15 or 35 in wrong subtree
• Confusing traversal order
• Listing nodes unsorted in output