Looking at binary trees in C++

published at 22.10.2025 13:55 by Jens Weller
Save to Instapaper Pocket

I'm in the process of preparing a quick talk on trees in C++ for Meeting C++ 2025. In order to see what the web offers, I've searched exactly for this, "trees in C++".

This showed that most posts found by duckduckgo or google were about binary trees, and in particular the same or similar implementation of using raw pointers for the left/right elements in the tree. Including using new to allocate for the nodes, only some times the code also bothers with using delete. The basic node class looks like this:

class TreeNode {
public:
    int data;               // The value stored in the node
    TreeNode* left;         // Pointer to the left child
    TreeNode* right;        // Pointer to the right child

    // Constructor
    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

This class is not from the web, but as the web is full of these examples - also the AI Agents ("Chatbots") will give you this result when asking this question. The above class is from googles gemini, as its been one of the better responses. ChatGPT was the only bot tested to yield an example that has a memory leak. I'm moving on though, this post isn't about letting AI Agents write the code for you.

My goal was to see if there is a different way to implement the binary tree, mostly for fun. A downside of the simple solution with pointers is that every node gets to sit into its own allocation and will then offer lots of potential cache misses when the tree is traversed. Converting the raw pointers to unique_ptr won't help much with that. Something I should later give a try is actually using unique_ptr with an updated version of my pool for unique pointers.

But I like to use this as an opportunity to play around with an idea I saw in Vittorio Romeos CppCon Keynote about Data Oriented Design: rather then using a reference or pointer, one could use an index into a container. If you make this container hold optional, then even elements can be removed from the optional in the container without invalidating the other indexes. So one trade off for this implementation is, that the indexes have to stay valid. Hence the vector can grow when new elements are needed, but never delete elements from the vector it self. The optional is also only needed if you'd like to be able to delete elements in the vector, which later would get reused potentially. So you are getting close to what an allocator does. Which turns above class into this:

class TreeNodeOptional {
public:
    int data;               // The value stored in the node
    int left=-1;         // index to the left child
    int right=-1;        // index to the right child

    // Constructor
    TreeNodeOptional(int value) : data(value){}
};

You could use optional< int|size_t > for the left/right connections, but for this I decided to use -1 as the default for not assigend/null-state in the int. As this is still just for fun, I do not turn this into a template. Also this is the easier part. The pointer implementation reads straight forward, but holding everything in one vector and using indexes changes a few details:

class BinaryTreeOptional {
private:
    int root=-1;
    std::vector<std::optional< TreeNodeOptional>> nodes;

    // Helper function for recursive insertion
    size_t insertRecursive(int node, int value) {
        if (node == -1) {
            nodes.emplace_back(value);
            return nodes.size()-1;
        }

        // Simple insertion logic (e.g., for a Binary Search Tree)
        auto node_value = nodes[node]->data;
        if (value < node_value) {
            nodes[node]->left = insertRecursive(nodes[node]->left, value);
        } else if (value > node_value) {
            nodes[node]->right = insertRecursive(nodes[node]->right, value);
        }

        return node;
    }

    // Helper function for In-order traversal (Left -> Root -> Right)
    void inOrderRecursive(std::optional< TreeNodeOptional >& onode) {
        if (onode.has_value()) {
          auto& node = onode.value();
            if(node.left != -1)
              inOrderRecursive(nodes[node.left]);
            if(node.right!= -1)
              inOrderRecursive(nodes[node.right]);
        }
    }

public:
    // Public method to insert a value
    void insert(int value) {
        insertRecursive(root, value);
    }

    // Public method to perform In-order traversal
    void inOrderTraversal() {
        if(root != -1)
          inOrderRecursive(nodes[root]);
    }
};

And this then kinda boils down to the old advice to use std::vector when implementing containers in C++. This code runs at 1.3-1.7 faster than the naive pointer implementation the speedup gets bigger with more elements added to the tree. This was tested on clang 17, and yielded similar results on GCC 13.2.  The newest available compiler versions on quick-bench:

This all was a bit of a side quest while working on a talk, and being curious how the combination out of vector, optional and type would perform. I feel motivated to explore this more in the future, likely once I've got the time after Meeting C++ 2025. I've already mentioned the unique_ptr pool from the past, it should make the comparison more fair.

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!