Binary Search Tree (BST)

Binary Search Tree Model and Invariant

A binary search tree (BST) is a binary tree with an ordering invariant. Under the distinct-key policy used here, every key in a node's left subtree is smaller than the node key, and every key in its right subtree is greater. The rule applies recursively to every subtree.

        50
      /    \
    30      70
   /  \    /  \
 20   40  60   80

The tree shape depends on insertion order. The same keys can form a short tree or a chain. Therefore “BST search is O(log n)” is not an unconditional guarantee.

Representing Nodes with unique_ptr

#include <memory>
#include <utility>

struct Node {
    int key;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

    explicit Node(int value) : key(value) {}
};

Each node exclusively owns its children, so std::unique_ptr expresses the tree's ownership directly. When the root is destroyed, recursive member destruction releases all nodes. This avoids manual delete and the leak/double-delete risks of raw owning pointers. Learn the model in C++ smart pointers.

Non-owning observation may still use const Node* temporarily, but ownership remains with the unique pointers.

Insertion and Search

void insert(std::unique_ptr<Node>& root, int key) {
    if (!root) {
        root = std::make_unique<Node>(key);
    } else if (key < root->key) {
        insert(root->left, key);
    } else if (key > root->key) {
        insert(root->right, key);
    }
    // Equal keys are ignored by this explicit policy.
}

bool contains(const std::unique_ptr<Node>& root, int key) {
    if (!root) return false;
    if (key == root->key) return true;
    return key < root->key ? contains(root->left, key)
                           : contains(root->right, key);
}

Both operations follow one root-to-leaf path. Passing the owning pointer by reference lets insertion replace an empty child link. Search accepts a const reference because it does not change ownership or nodes.

Inorder, Preorder and Postorder Traversal

void inorder(const std::unique_ptr<Node>& root) {
    if (!root) return;
    inorder(root->left);
    std::cout << ' ' << root->key;
    inorder(root->right);
}

Each full traversal takes Θ(n) time because every node is visited once. Recursive auxiliary stack space is O(h).

The Three BST Deletion Cases

1. No child: replace the owning link with null.
2. One child: move that child into the target's owning link.
3. Two children: copy the smallest key in the right subtree (inorder successor), then delete that key from the right subtree.

int minimum_key(const Node* node) {
    while (node->left) node = node->left.get();
    return node->key;
}

void erase(std::unique_ptr<Node>& root, int key) {
    if (!root) return;
    if (key < root->key) erase(root->left, key);
    else if (key > root->key) erase(root->right, key);
    else if (!root->left) root = std::move(root->right);
    else if (!root->right) root = std::move(root->left);
    else {
        const int successor = minimum_key(root->right.get());
        root->key = successor;
        erase(root->right, successor);
    }
}

Moving a unique pointer transfers ownership safely. The successor has no left child, so the recursive deletion reduces to a simpler case.

Height, Complexity and Balancing

In a reasonably balanced tree, h=Θ(log n). Inserting already sorted keys into this unbalanced BST makes h=Θ(n), turning operations linear and risking deep recursion. AVL and red-black trees use rotations and balance metadata to control height. Standard std::set and std::map provide logarithmic search/insert/erase complexity requirements; use them instead of a teaching BST when their interface fits. See set and map.

Complete Modern C++ BST Lab

#include <iostream>
#include <memory>
#include <utility>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : key(value) {}
};

void insert(std::unique_ptr<Node>& root, int key) {
    if (!root) root = std::make_unique<Node>(key);
    else if (key < root->key) insert(root->left, key);
    else if (key > root->key) insert(root->right, key);
}

bool contains(const std::unique_ptr<Node>& root, int key) {
    if (!root) return false;
    if (key == root->key) return true;
    return key < root->key ? contains(root->left, key)
                           : contains(root->right, key);
}

void inorder(const std::unique_ptr<Node>& root) {
    if (!root) return;
    inorder(root->left);
    std::cout << ' ' << root->key;
    inorder(root->right);
}

int minimum_key(const Node* node) {
    while (node->left) node = node->left.get();
    return node->key;
}

void erase(std::unique_ptr<Node>& root, int key) {
    if (!root) return;
    if (key < root->key) erase(root->left, key);
    else if (key > root->key) erase(root->right, key);
    else if (!root->left) root = std::move(root->right);
    else if (!root->right) root = std::move(root->left);
    else {
        int successor = minimum_key(root->right.get());
        root->key = successor;
        erase(root->right, successor);
    }
}

int main() {
    std::unique_ptr<Node> root;
    for (int key : {50, 30, 70, 20, 40, 60, 80}) insert(root, key);
    std::cout << "Inorder:"; inorder(root); std::cout << '\n';
    std::cout << "Contains 60: " << std::boolalpha
              << contains(root, 60) << '\n';
    erase(root, 30);
    std::cout << "After deleting 30:"; inorder(root); std::cout << '\n';
}

Deleting 30 exercises the two-child case: 40 is its inorder successor.

Common Mistakes, Tests and Practice

Test empty-tree search/delete, root deletion, leaf, one child, two children, absent key, duplicate insertion and skewed input. Practice iterative search, height calculation, validation with lower/upper bounds, predecessor/successor and level-order traversal.

Authoritative References

• NIST DADS: binary search tree
• NIST DADS: binary tree
• NIST DADS: search-tree property

The definitions and ordering property were checked against these references. Continue with smart pointers and ordered containers.