Binary Search Tree and implementation in C++

A binary search tree (BST) is a binary tree built around one simple rule: each node stores a value, every value in its left subtree is smaller, and every value in its right subtree is larger. That rule is what makes the structure useful. It turns the tree into a dynamic ordered container, so searching, inserting, and deleting all follow the same left-or-right logic instead of scanning every element one by one .

This page has three threads:

1. The ordering rule that defines a BST.

2. The core operations: search, insertion, deletion, and traversal.

3. A concrete C++ implementation and the design choices that make it correct and safe.

The key mental model is this: every node acts like a decision point. If the target is smaller, go left. If larger, go right. Then the same rule repeats again inside that subtree. A BST is not just a tree with two children per node. It is a tree where each node partitions the remaining values into a smaller-left side and a larger-right side, recursively all the way down .

The binary search tree invariant

The defining property of a BST is called its invariant:

• For any node with key :

  • every key in the left subtree is less than

  • every key in the right subtree is greater than

This is not only a rule about a node's immediate children. It applies to the entire left and right subtrees. That is the part beginners often miss.

For example, if a node contains , then the left child might be and the right child might be . But the rule goes deeper than that:

• everything anywhere under the left subtree must be less than

• everything anywhere under the right subtree must be greater than

That recursive ordering is why search works so cleanly. Suppose you are looking for :

• compare with the root

• if is smaller, go left

• if is larger, go right

• repeat until you find it or hit nullptr

At each step, you are not just moving randomly through the tree. You are discarding an entire subtree that cannot possibly contain the answer. Conceptually, that is the tree version of binary search on a sorted array, although the actual speed depends on the tree's shape .

The trap is to think "left child smaller, right child larger" is enough. It is not. A tree can satisfy that local pattern and still fail to be a BST if some deeper descendant breaks the global rule.

How a BST differs from a plain binary tree

A plain binary tree only says that each node has at most two children. It says nothing about the values.

A binary search tree adds an ordering constraint.

That difference changes everything.

In a plain binary tree, if you want to find a value, you may need to inspect many nodes because there is no ordering information to guide you. In a BST, the ordering property tells you which side is worth exploring.

The recursive nature matters too. Every subtree of a BST is itself a BST. That means once you understand the rule at one node, you understand the rule everywhere. Search, insertion, deletion, and traversal all reuse the same idea.

One especially important consequence is inorder traversal:

1. visit the left subtree

2. visit the node

3. visit the right subtree

Because left values are smaller and right values are larger, inorder traversal of a BST prints the keys in sorted order .

Core BST operations step by step

A BST usually supports four core operations:

• search

• insert

• delete

• traverse

All four come directly from the ordering invariant.

• Search uses comparisons to choose left or right.

• Insert follows the same path as search until it finds an empty spot.

• Delete first finds the node, then repairs the tree while preserving the invariant.

• Traversal visits nodes in a systematic order for printing, exporting, or cleanup.

Three of these are straightforward once the invariant is clear. Deletion is the one that forces you to think carefully, because removing a node can change the structure in several different ways .

The best way to learn the code is in this order:

1. understand the left-or-right decision rule

2. write search

3. adapt that logic into insert

4. learn deletion by cases

5. add traversals

6. package everything inside a C++ class

Searching and inserting values

Search is the cleanest BST operation.

Given a target key:

1. if the current node is nullptr, the key is not in the tree

2. if the current node's key matches, stop

3. if the target is smaller, search the left subtree

4. if the target is larger, search the right subtree

That is all.

Insertion is almost the same. The only difference is what happens when you reach nullptr: instead of reporting "not found", you create a new node there .

A small example helps. Insert these values in order:

• 50 becomes the root

• 30 < 50, so it goes left of 50

• 70 > 50, so it goes right of 50

• 20 < 50, then 20 < 30, so it becomes left of 30

• and so on

The algorithm is just repeated comparison.

Duplicate values

A BST implementation must choose a duplicate policy. Common choices are:

• reject duplicates

• count duplicates in each node

• always send duplicates to one side, such as the right

What matters is consistency. If you do not define the policy, your tree logic becomes ambiguous.

Here is the core logic in compact recursive form:

Node* search(Node* root, int key) {
    if (root == nullptr || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);

    return search(root->right, key);
}

Node* insert(Node* root, int key) {
    if (root == nullptr)
        return new Node(key);

    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);

    return root;
}

The most important line for insertion is not the comparison. It is the reassignment:

• root->left = insert(root->left, key);

• root->right = insert(root->right, key);

That is what reconnects the updated subtree back to its parent.

Deleting a node: leaf, one child, and two children

Deletion is the operation that reveals whether you really understand a BST.

Search and insert mainly follow the structure. Deletion has to repair it.

There are three cases :

1. Deleting a leaf node

A leaf has no children.

This is the simplest case. You just remove the node and set the parent's corresponding pointer to nullptr.

Example: deleting 20 from a tree where 20 has no children.

2. Deleting a node with one child

If the node has exactly one child, remove the node and connect its parent directly to that child.

So if node 30 has only a right child 40, deleting 30 means 40 takes its place.

The idea is simple: skip over the deleted node, but keep the subtree below it.

3. Deleting a node with two children

This is the interesting case.

You cannot simply remove the node, because that would disconnect both subtrees. Instead, you replace the node's value with a nearby value that preserves the BST order.

The most common choice is the inorder successor:

• the smallest value in the node's right subtree

Why that value?

Because it is:

• larger than everything in the left subtree

• the smallest value that is still larger than the deleted node

So it fits perfectly in the deleted node's position.

The process is:

1. find the node to delete

2. find its inorder successor by going to the right child, then as far left as possible

3. copy the successor's value into the node

4. delete the successor from the right subtree

That last deletion is easier than it sounds, because the successor cannot have a left child. If it did, it would not be the leftmost node.

Here is the recursive shape:

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

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        } else if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        } else {
            Node* temp = findMin(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }

    return root;
}

The tricky line is this one:

• root->right = deleteNode(root->right, temp->data);

After copying the successor's value, you still must remove the original successor node from the right subtree. Otherwise you create a duplicate.

Tree traversals and sorted output

A traversal is a systematic way to visit every node.

The three classic depth-first traversals are:

1. Preorder: node, left, right

2. Inorder: left, node, right

3. Postorder: left, right, node

In code, they are usually written recursively because the tree itself is recursive.

Why inorder is sorted

This is one of the nicest properties of a BST.

• the left subtree contains smaller keys

• then you visit the current node

• then the right subtree contains larger keys

So inorder traversal naturally outputs the keys in ascending order .

That makes inorder traversal useful for:

• printing values in sorted order

• exporting the tree as a sorted sequence

• checking whether the BST ordering is correct

Why postorder is useful for cleanup

If you want to free all dynamically allocated nodes, postorder is the safe traversal:

1. delete left subtree

2. delete right subtree

3. delete current node

That way you never delete a node before its children have been handled.

Example implementations:

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

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

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

The pattern is always the same. Only the position of the "visit this node" action changes.

Implementing a BST node and class in C++

Now the data-structure idea turns into C++ code.

At minimum, each node needs:

• a stored key

• a pointer to the left child

• a pointer to the right child

A tree class usually also keeps:

• a pointer to the root node

• public methods like insert, search, remove, and inorder

• private helper functions that operate recursively on Node*

This split is useful because the public interface stays simple, while the recursive details stay internal.

Designing the Node structure and tree interface

A minimal node can look like this:

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

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

That constructor matters. It ensures every new node starts with valid child pointers set to nullptr.

Then a basic BST class might look like this:

class BST {
private:
    Node* root;

    Node* insert(Node* node, int key);
    Node* search(Node* node, int key);
    Node* deleteNode(Node* node, int key);
    Node* findMin(Node* node);
    void inorder(Node* node);
    void destroy(Node* node);

public:
    BST() : root(nullptr) {}
    ~BST() { destroy(root); }

    void insert(int key);
    bool search(int key);
    void remove(int key);
    void inorder();
};

The main design idea is that many helper functions:

• take a Node* representing the root of a subtree

• return a possibly updated Node*

That return value is essential for mutation.

Why? Because when recursion inserts or deletes inside a subtree, the subtree's root may change. For example:

• inserting into an empty subtree changes nullptr into a real node

• deleting a node with one child may replace that node with its child

So recursive tree code often works like this:

node->left = insert(node->left, key);

That is how links are rewired safely on the way back up the recursion.

A complete recursive BST implementation in C++

Below is a compact but complete recursive BST in modern C++.

#include <iostream>
using namespace std;

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

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

class BST {
private:
    Node* root;

    Node* insert(Node* node, int key) {
        if (node == nullptr)
            return new Node(key);

        if (key < node->data)
            node->left = insert(node->left, key);
        else if (key > node->data)
            node->right = insert(node->right, key);

        return node;
    }

    Node* search(Node* node, int key) {
        if (node == nullptr || node->data == key)
            return node;

        if (key < node->data)
            return search(node->left, key);

        return search(node->right, key);
    }

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

    Node* deleteNode(Node* node, int key) {
        if (node == nullptr)
            return nullptr;

        if (key < node->data) {
            node->left = deleteNode(node->left, key);
        } else if (key > node->data) {
            node->right = deleteNode(node->right, key);
        } else {
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                return nullptr;
            } else if (node->left == nullptr) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                Node* temp = node->left;
                delete node;
                return temp;
            } else {
                Node* temp = findMin(node->right);
                node->data = temp->data;
                node->right = deleteNode(node->right, temp->data);
            }
        }

        return node;
    }

    void inorder(Node* node) {
        if (node == nullptr)
            return;

        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }

    void destroy(Node* node) {
        if (node == nullptr)
            return;

        destroy(node->left);
        destroy(node->right);
        delete node;
    }

public:
    BST() : root(nullptr) {}

    ~BST() {
        destroy(root);
    }

    void insert(int key) {
        root = insert(root, key);
    }

    bool search(int key) {
        return search(root, key) != nullptr;
    }

    void remove(int key) {
        root = deleteNode(root, key);
    }

    void inorder() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    BST tree;

    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(60);
    tree.insert(80);

    tree.inorder();

    tree.remove(50);
    tree.inorder();

    cout << (tree.search(60) ? "Found" : "Not found") << endl;
}

A few details matter more than they first appear:

• Base cases stop recursion when node == nullptr.

• insert and deleteNode return subtree roots so parents can reconnect correctly.

• findMin walks left until it cannot go farther, which matches the BST property .

• Nodes created with new must eventually be released with delete, or memory leaks follow.

If the code feels repetitive, that is actually a good sign. BST algorithms are variations on the same recursive structure.

Performance, edge cases, and when a BST goes wrong

BST performance is controlled by one quantity: the tree's height, often written as .

For search, insertion, and deletion, the running time is typically proportional to because each operation follows one path from the root downward.

So the real question is: how tall is the tree?

• In a reasonably balanced tree, height is about

• In a badly skewed tree, height can become

That means:

The classic failure case is inserting already sorted data into a plain BST:

Each new value goes to the right of the previous one. The tree stops looking like a branching structure and starts looking like a linked list. At that point, the BST has lost most of its advantage .

That is why self-balancing trees exist.

• AVL trees keep height tightly controlled with rotations.

• Red-Black trees also rebalance, with slightly looser constraints but efficient guarantees.

A plain BST is excellent for learning and useful in some practical settings, but it does not stay balanced automatically.

Common implementation mistakes in C++

Most BST bugs are not mysterious. They come from a handful of recurring mistakes.

1. Forgetting to return the updated subtree root

This is the big one.

Wrong mental model: "I inserted into the left side, so the tree changed automatically."

Correct mental model: recursive mutation often creates a new subtree root for that branch, and the parent must store it.

That is why code like this matters:

node->left = insert(node->left, key);

If you forget the assignment, the new node may be created but never linked into the tree.

2. Mishandling deletion links

Deletion often fails because the programmer deletes a node but does not reconnect its child properly.

Checklist:

• if no children: return nullptr

• if one child: return that child

• if two children: copy successor value, then delete successor

If one of those return paths is wrong, the structure breaks.

3. Dereferencing nullptr

Any recursive helper can eventually receive nullptr. If your code reads node->data before checking node == nullptr, it can crash.

Base cases come first.

4. Leaking memory

If you use new, you are responsible for delete.

Common leak points:

• deleting a node incorrectly

• never freeing the whole tree

• overwriting pointers without releasing the old node

A destructor with postorder cleanup is the standard fix.

5. Ignoring duplicates

If the code does not define what to do when key == node->data, bugs appear quickly:

• infinite recursion in some bad implementations

• inconsistent structure

• unexpected missing inserts

Pick a policy and implement it explicitly.

6. Assuming the tree stays balanced

A BST can degrade badly depending on insertion order. If operations suddenly feel slow, the logic may be correct but the shape may be poor.

A good debugging checklist is:

• Is the BST invariant preserved after every insert and delete?

• Does every mutating helper return the correct subtree root?

• Are all nullptr cases handled before pointer dereference?

• Is every removed node freed exactly once?

• Is the duplicate policy consistent?

• Am I expecting behavior from a tree that has become skewed?

Those questions catch most real beginner errors.