C++ Binary Trees

A binary tree is a data structure made of nodes where each node can have up to two children. The two child links are usually called left and right.

Binary trees are useful when data has a natural branching shape. A common beginner example is a binary search tree, where smaller values go to the left and larger values go to the right.

Tree Words

The first node in a tree is the root. A node below another node is a child. A node with no children is a leaf. Each step downward moves to a lower level of the tree.

In a binary tree, each node stores a value and two pointers:

• left points to the left child, or nullptr if there is none.
• right points to the right child, or nullptr if there is none.

Example: Binary Search Tree

This example builds a small binary search tree. It inserts values, prints them with two traversal orders, and searches for two values.

#include <iostream>

class BinarySearchTree {
private:
    struct Node {
        int value;
        Node* left;
        Node* right;
    };

    Node* root;

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

        if (value < node->value) {
            node->left = insert(node->left, value);
        } else if (value > node->value) {
            node->right = insert(node->right, value);
        }

        return node;
    }

    bool contains(Node* node, int value) const {
        if (node == nullptr) {
            return false;
        }

        if (value == node->value) {
            return true;
        }

        if (value < node->value) {
            return contains(node->left, value);
        }

        return contains(node->right, value);
    }

    void printValue(int value, bool& first) const {
        if (!first) {
            std::cout << " ";
        }

        std::cout << value;
        first = false;
    }

    void printInOrder(Node* node, bool& first) const {
        if (node == nullptr) {
            return;
        }

        printInOrder(node->left, first);
        printValue(node->value, first);
        printInOrder(node->right, first);
    }

    void printPreOrder(Node* node, bool& first) const {
        if (node == nullptr) {
            return;
        }

        printValue(node->value, first);
        printPreOrder(node->left, first);
        printPreOrder(node->right, first);
    }

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

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

public:
    BinarySearchTree(void) {
        root = nullptr;
    }

    ~BinarySearchTree(void) {
        clear(root);
    }

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

    bool contains(int value) const {
        return contains(root, value);
    }

    void printInOrder(void) const {
        bool first = true;
        printInOrder(root, first);
        std::cout << std::endl;
    }

    void printPreOrder(void) const {
        bool first = true;
        printPreOrder(root, first);
        std::cout << std::endl;
    }
};

int main(void) {
    BinarySearchTree tree;
    int values[] = {50, 30, 70, 20, 40, 60, 80};

    for (int value : values) {
        tree.insert(value);
    }

    std::cout << "In order: ";
    tree.printInOrder();

    std::cout << "Pre order: ";
    tree.printPreOrder();

    std::cout << "Contains 60: " << tree.contains(60) << std::endl;
    std::cout << "Contains 25: " << tree.contains(25) << std::endl;

    return 0;
}

Output:

In order: 20 30 40 50 60 70 80
Pre order: 50 30 20 40 70 60 80
Contains 60: 1
Contains 25: 0

How Insertion Works

The tree starts with root set to nullptr. The first inserted value becomes the root. After that, each new value is compared with the current node.

If the new value is smaller, insertion continues into the left child. If it is larger, insertion continues into the right child. When the code reaches a nullptr link, it creates a new node there.

This example ignores duplicate values. If a value is equal to the current node’s value, the function simply returns the existing node.

Traversal Orders

Traversal means visiting every node in a tree. The example uses recursion because each subtree is itself a smaller tree.

Traversal	Order	Common use
In-order	Left, current node, right	Prints a binary search tree in sorted order
Pre-order	Current node, left, right	Useful when you need to process a parent before its children

For the inserted values, in-order traversal prints 20 30 40 50 60 70 80 because the binary search tree rule keeps smaller values on the left and larger values on the right.

Searching a Tree

The contains() function follows the same comparison rule as insertion. If the target is smaller than the current value, it searches left. If the target is larger, it searches right. If it reaches nullptr, the value is not in the tree.

A well-balanced binary search tree can find values quickly because each comparison can skip a whole branch. However, if values are inserted in sorted order, the tree can become shaped like a linked list, which is slower.

Memory Cleanup

Each node is created with new, so the tree must release each node with delete. The clear() function deletes the left and right subtrees before deleting the current node. The destructor calls clear() automatically when tree goes out of scope.

Takeaway: a binary tree stores each value in a node with up to two child links, and traversal is the basic way to visit every value.