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.