Implementing a Binary Search Tree in C++

What Is a Binary Search Tree?

A Binary Search Tree (BST) is a node-based data structure where each node has at most two children. It satisfies one key property: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property makes search, insertion, and deletion operations very efficient.

The Node Structure

Let's start by defining the basic building block — a tree node:

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Insertion

Insertion follows the BST property recursively: go left if the value is smaller, go right if larger.

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

Search

Searching is similarly recursive and runs in O(h) time, where h is the tree height:

bool search(Node* root, int val) {
    if (root == nullptr) return false;
    if (root->data == val) return true;
    if (val < root->data) return search(root->left, val);
    return search(root->right, val);
}

Tree Traversals

There are three common ways to traverse a BST, each visiting nodes in a different order:

In-Order (Left → Node → Right)

Visits nodes in sorted ascending order — very useful for BSTs.

void inOrder(Node* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    std::cout << root->data << " ";
    inOrder(root->right);
}

Pre-Order and Post-Order

void preOrder(Node* root) { // Node → Left → Right
    if (!root) return;
    std::cout << root->data << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void postOrder(Node* root) { // Left → Right → Node
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    std::cout << root->data << " ";
}

Deletion

Deletion is the trickiest operation. There are three cases to handle:

1. Node is a leaf — simply remove it.
2. Node has one child — replace the node with its child.
3. Node has two children — replace the node's value with the in-order successor (smallest value in right subtree), then delete the successor.

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* deleteNode(Node* root, int val) {
    if (root == nullptr) return nullptr;

    if (val < root->data) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        if (!root->left) { Node* tmp = root->right; delete root; return tmp; }
        if (!root->right) { Node* tmp = root->left; delete root; return tmp; }
        Node* successor = findMin(root->right);
        root->data = successor->data;
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

Time Complexity Summary

Operation	Average Case	Worst Case (Skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

To avoid worst-case behavior, consider using self-balancing trees like AVL trees or Red-Black trees — or use std::set / std::map from the STL, which are typically implemented as balanced BSTs.

Putting It All Together

The BST is a foundational data structure worth understanding deeply. Once you're comfortable with it, concepts like heaps, tries, and self-balancing trees will feel much more approachable.