BST Insert Operation in DSA C++

Mental Model

A binary search tree keeps smaller values on the left and bigger values on the right. Inserting means finding the right empty spot to keep this order.

Analogy: Imagine placing books on a shelf where all books with smaller titles go to the left side and bigger titles go to the right side. You find the right empty spot by comparing titles one by one.

    5
   / \
  3   7
 / \   \
2   4   8
↑ root

Dry Run Walkthrough

Input: Insert value 6 into BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8

Goal: Add 6 in the correct position to keep BST order

Step 1: Compare 6 with root 5, move right because 6 > 5

5 -> [curr->7]
/ \   \
3   7   8
/ \     
2   4    

Why: We go right because 6 is bigger than 5

Step 2: Compare 6 with 7, move left because 6 < 7

5 -> 7 -> [curr->null]
/ \   \
3   7   8
/ \     
2   4    

Why: We go left because 6 is smaller than 7

Step 3: Insert 6 as left child of 7

5 -> 7 -> 6
/ \   / \
3   7 6   8
/ \     
2   4    

Why: Found empty spot, insert 6 here to keep BST order

Result:

5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* insertBST(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val); // create new node when spot found
    }
    if (val < root->val) {
        root->left = insertBST(root->left, val); // go left
    } else {
        root->right = insertBST(root->right, val); // go right
    }
    return root; // return unchanged root
}

void printInOrder(Node* root) {
    if (root == nullptr) return;
    printInOrder(root->left);
    cout << root->val << " ";
    printInOrder(root->right);
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(7);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->right = new Node(8);

    root = insertBST(root, 6);

    printInOrder(root);
    cout << endl;
    return 0;
}

if (root == nullptr) { return new Node(val); }

create new node when empty spot found

if (val < root->val) { root->left = insertBST(root->left, val); }

go left if value smaller

else { root->right = insertBST(root->right, val); }

go right if value bigger or equal

return root;

return current root after insertion

Output

2 3 4 5 6 7 8 

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 array insertions which can be O(n) due to shifting, BST insert is faster if tree is balanced

Edge Cases

Empty tree (root is nullptr)

New node becomes the root

DSA C++

if (root == nullptr) { return new Node(val); }

Insert duplicate value

Duplicates go to the right subtree by this code logic

DSA C++

else { root->right = insertBST(root->right, val); }

Insert smallest or largest value

Insertion goes to leftmost or rightmost leaf respectively

DSA C++

recursive calls until root == nullptr

When to Use This Pattern

When you need to add a value to a sorted tree structure while keeping order, use BST insert to find the correct spot efficiently.

Common Mistakes

Mistake: Not updating the parent's left or right pointer after recursive insert
Fix: Assign the recursive call result back to root->left or root->right

Mistake: Inserting duplicates on the left causing imbalance
Fix: Decide a consistent rule, here duplicates go right

Summary

Inserts a value into the binary search tree keeping its order.

Use when you want to add elements to a BST without breaking its sorted property.

The key is to find the empty spot by comparing values and moving left or right.