Generic Binary Tree

Question

I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am now writing a binary tree data structure using linked list from scratch. This data structure was a bit more difficult for me so my code may not be as good as the others I have posted here.

I have tested my class that I wrote and everything seems to be working fine but I want to see if there are any bugs or some areas of the code I could improve on. Specifically, I am a bit suspicious if my traversal functions are correct because my in-order traversal and post-order traversal output the same results.

Here is my header file:

#ifndef BinaryTree_h
#define BinaryTree_h

template <class T>
class BinaryTree {
private:
    struct TreeNode {
        T data;
        TreeNode *left = nullptr;
        TreeNode *right = nullptr;
        TreeNode(T x): data(x), left(nullptr), right(nullptr){}
    };
    TreeNode *root = nullptr;

    // This is used to free the memory
    void deleteTree(TreeNode *node) {
        if(node == nullptr) {
            return;
        }
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }

    // This is used for the copy constructor
    void copyTree(TreeNode *thisRoot, TreeNode *sourceRoot) {
        if(sourceRoot == nullptr) {
            thisRoot = nullptr;
        }
        else {
            thisRoot = new TreeNode;
            thisRoot->data = sourceRoot->data;
            copyTree(thisRoot->left, thisRoot->left);
            copyTree(thisRoot->right, thisRoot->right);
        }
    }

    // These functions are for creating the tree
    void insertPrivate(TreeNode *&root, const T &theData);
    void insertPrivate(TreeNode *&root, T &&theData);

    // Traversal functions for printing the nodes
    void inorderTraversal(BinaryTree::TreeNode* root);
    void pretorderTraversal(BinaryTree::TreeNode* root);
    void postorderTraversal(BinaryTree::TreeNode* root);

public:
    // Constructors
    BinaryTree() = default;                                                       // empty constructor
    BinaryTree(BinaryTree const &source);                                         // copy constructor

    // Rule of 5
    BinaryTree(BinaryTree &&move) noexcept;                                       // move constuctor
    BinaryTree& operator=(BinaryTree &&move) noexcept;                            // move assignment operator
    ~BinaryTree();                                                                // destructor

    // Overload operators
    BinaryTree& operator=(BinaryTree const &rhs);

    // Member functions
    void insert(const T &theData);
    void insert(T &&theData);

    void printInorder();
    void printPreorder();
    void printPostorder();


};

template <class T>
BinaryTree<T>::BinaryTree(BinaryTree<T> const &source)  {
    if(source.root == nullptr) {
        root = nullptr;
    }
    else {
        copyTree(this->root, source.root);
    }
}

template <class T>
BinaryTree<T>::BinaryTree(BinaryTree &&move) noexcept {
    move.swap(*this);
}

template <class T>
BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
BinaryTree<T>::~BinaryTree() {
    deleteTree(root);
}

template <class T>
BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree const &rhs) {
    BinaryTree copy(rhs);
    swap(copy);
    return *this;
}

template <class T>
void BinaryTree<T>::insertPrivate(TreeNode *&root, const T &theData) {
    if(root == nullptr) {
        root = new TreeNode{theData};
        return;
    }
    else if(theData < root->data) {
        insertPrivate(root->left, theData);
    }
    else {
        insertPrivate(root->right, theData);
    }
}

template <class T>
void BinaryTree<T>::insertPrivate(TreeNode *&root, T &&theData) {
    std::cout << "Using with move" << std::endl;
    if(root == nullptr) {
        root = new TreeNode{std::move(theData)};
        return;
    }
    else if(theData < root->data) {
        insertPrivate(root->left, std::move(theData));
    }
    else {
        insertPrivate(root->right, std::move(theData));
    }
}

template <class T>
void BinaryTree<T>::insert(const T &theData) {
    insertPrivate(root, theData);
}

template <class T>
void BinaryTree<T>::insert(T &&theData) {
    insertPrivate(root, theData);
}

template <class T>
void BinaryTree<T>::inorderTraversal(BinaryTree<T>::TreeNode *root)  {
    // The items in the left subtree are printed first, followed
    // by the item in the root node, followed by the items in
    // the right subtree.
    if(root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

template <class T>
void BinaryTree<T>::pretorderTraversal(BinaryTree<T>::TreeNode *root)  {
    // Print all the items in the tree to which root points.
    // The item in the root is printed first, followed by the
    // items in the left subtree and then the items in the
    // right subtree.
    if(root != nullptr) {
        std::cout << root->data << " ";
        pretorderTraversal(root->left);
        pretorderTraversal(root->right);
    }
}

template <class T>
void BinaryTree<T>::postorderTraversal(BinaryTree<T>::TreeNode *root)  {
    // Print all the items in the tree to which root points.
    // The items in the left subtree are printed first, followed
    // by the items in the right subtree and then the item in the
    // root node.
    if(root != nullptr) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

template <class T>
void BinaryTree<T>::printInorder() {
    inorderTraversal(root);
}

template <class T>
void BinaryTree<T>::printPreorder() {
    pretorderTraversal(root);
}

template <class T>
void BinaryTree<T>::printPostorder() {
    postorderTraversal(root);
}

#endif /* BinaryTree_h */

Here is the main.cpp file that tests this class:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <ostream>
#include <iosfwd>
#include "BinaryTree.h"

int main(int argc, const char * argv[]) {
        ////////////////////////////////////////////////////////////////////////////
    ///////////////////////////// Binary Tree //////////////////////////////////
    ////////////////////////////////////////////////////////////////////////////
    BinaryTree<int> obj;
    obj.insert(10);
    obj.insert(8);
    obj.insert(6);
    obj.insert(4);
    obj.insert(2);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Displaying Tree Contents---------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.printInorder();
    std::cout << std::endl;
    obj.printPreorder();
    std::cout << std::endl;
    obj.printPostorder();



    return 0;
}

Answer 1

Use std::unique_ptr!

I see two potential memory leaks in the code, and both of them would have been prevented by using std::unique_ptr.

1. In copyTree, a new TreeNode (or nullptr) is assigned to the local variable thisRoot. Since thisRoot isn't a reference, the value won't be propagated to the caller, so if an allocation happens, it will leak.

   Using std::unique_ptr would have prevented this: As std::unique_ptr isn't copyable, it isn't possible to pass it directly to this function. It would need to be std::moved in, at which point it should be obvious that there is a problem with the function.

2. Again in copyTree, if new TreeNode throws (e.g. because the system ran out of memory), already allocated nodes will not be released (remember: If a constructor throws, the destructor will not be called)!

   Again, std::unique_ptr to the rescue! BinaryTrees destructor won't be called, but the destructors of already constructed members (like root) will be, so the memory would be nicely cleaned up.

Quick guide of "How to use std::unique_ptr for this code"

Step 1: Replace owning TreeNode* storage with std::unique_ptr<TreeNode>. Occurances: TreeNode::left, TreeNode::right and BinaryTree<T>::root.

Step 2: Replace TreeNode*& (note the reference!) function parameters with std::unique_ptr<TreeNode>&. (Those are the functions that somehow change ownership, e.g. by creating new TreeNodes).

Step 3: Fix callsites where now a std::unique_ptr<TreeNode> gets passed, but a TreeNode* is expected, by calling .get() on the std::unique_ptr<TreeNode> object. (get() returns a raw TreeNode* to the managed TreeNode object).

Step 4: Replace calls to new TreeNode(...) with calls to std::make_unique<TreeNode>(...).

Why call std::make_unique<TreeNode>(...) instead of std::unique_ptr{ new TreeNode{ ... } }? Because the latter might leak memory in case of an exception! std::make_unique handles that case for you.

Idiomatically, a std::unique_ptr<T> means "I own this T", whereas a (non-owning) T* just refers to an instance of a T. So, pass a T* if the called function doesn't become the new owner of that T. If the ownership is to be transferred, use std::move on the std::unique_ptr<T>.

Recursion

While recursion isn't that big of a deal in a balanced binary tree (as that only recurses up to depth \$\mathcal{O}(\log n)\$), this tree isn't balanced! In the worst case (as your main does), this means recursion will go to depth \$\mathcal{O}(n)\$.

Why is this important? It means that, depending on the stored data and its insertion order, the member functions using recursion might overflow the stack. And there are only two member functions not using recursion (directly or indirectly), and these are the default constructor and the move constructor (I don't count the move assignment operator might cause a call to the destructor if the right hand side operand was a temporary).

What are the options for this?

1. Hope that there will never be enough data inside the tree to cause this. This won't scale.
2. Balance the tree and hope that memory runs out before the recursion causes issues. Might work in practice, but just moves the problem around.
3. Use different iteration strategies (e.g. pushing nodes to be traversed into a queue/onto a stack/... to manually keep track and not exhausting the call stack).

I strongly recommend option #3.

The problem with recursion

In the general case, a function needs to somehow preserve its state (values of local variables) before calling another function. This is usually done by storing them on the callstack. This callstack is usually provided by the OS and has a limited size, e.g. around 1 MiB for Windows (other platforms will differ).

Recursive calls also need to store their state like this, so the amount of space required on the callstack scales linearly with the amount of nested recursion calls (I'm ignoring Tail Call Optimization for now, since it isn't applicable on most of the binary tree recursive calls).

Some math: Assuming we have the full callstack for ourselves (note: we usually don't), this means we can store up to \$\text{Callstack size} / \text{sizeof(TreeNode*)} = 2^{20} \text{Bytes} / 8 \text{Bytes} = 2^{17} = 131.072\$ TreeNode* on the callstack before we run out of space (this is for 64 bit OSes, double the amount for 32 bit OSes, as there sizeof(TreeNode *) == 4 Bytes).

For an unbalanced tree, this means having a depth of more than 131.072 will be certain trouble, which can be achieved with an highly unbalanced arrangement of 131.073 nodes.

But wait, didn't I mention we don't usually have the whole callstack for ourselves? So this number is just the best case scenario of worst case imbalance. We might hit the limits of the callstack much earlier.

This isn't that big of a deal in a balanced tree, as those have a depth of \$\mathcal{O}(\log_{2} n)\$, so to reach a depth of 131.072 would require \$2^{131.072 + 1}\$ nodes, which is more than the addressable amount of memory (\$2^{64}\$ Bytes at most, more likely below \$2^{48}\$ on consumer hardware). (That doesn't mean it's impossible to overflow the callstack with a balanced tree, just highly unlikely).

Caution

Though I used an amount of 1 MiB of callstack space, this is only the case on a specific platform: Windows. In other environments (e.g. embedded), this number might be much lower (total RAM might be less than 1 kiB!). Thus, it might be better to keep track of that recursion state manually, in order to prevent (call-)stack overflow errors on platforms with less callstack space.

Example (just replacing recursion with iteration):

template <class T>
void BinaryTree<T>::preorderTraversal()  {
    if(root == nullptr) return;

    auto to_be_visited = std::stack<TreeNode*>{}; // storage somewhere on the heap
    to_be_visited.push(root);

    while(!to_be_visited.empty()) {
        auto node = to_be_visited.top();
        to_be_visited.pop();

        std::cout << node->data << " ";
        if(node->right) to_be_visited.push(node->right);
        if(node->left) to_be_visited.push(node->left);
    }
}

Iteration

The current iteration member functions only support printing values to std::cout. This means that there is no real way to see what data is actually stored inside the tree for other purposes. I've seen two iteration designs that allow custom behavior for each node:

1. Accept a function object and apply it on every node in traversal order.

   This usually works fine, but needs lots of bookkeeping on the user's side if non-trivial operations are being performed.

2. Using iterators.

   This approach might be harder to implement, but it has some benefits as well: It means the tree can easily be combined with standard library algorithms or ranged for loops.

Examples (assuming std::unique_ptr is used, only pre-order traversal covered):

option #1

// implementation
template <class T>
template <typename Callable>
void BinaryTree<T>::pre_order(Callable&& visit)  {
    if(root == nullptr) return;

    auto to_be_visited = std::stack<TreeNode*>{}; // storage somewhere on the heap
    to_be_visited.push(root.get());

    while(!to_be_visited.empty()) {
        auto node = to_be_visited.top();
        to_be_visited.pop();

        visit(node->data);
        if(node->right) to_be_visited.push(node->right.get());
        if(node->left) to_be_visited.push(node->left.get());
    }
}

// usage
tree.pre_order([](auto&& elem) { std::cout << elem << " "; });

option #2

// implementation (not in order! Will need rearrangement or forward declarations to compile)

template<typename T>
class pre_order_range { // could be nested inside BinaryTree, then the template isn't necessary
    BinaryTree<T>::TreeNode* root;

public:
    pre_order_range(BinaryTree<T>::TreeNode* root) : root{root} {}

    auto begin() const { return pre_order_iterator{root}; }
    auto cbegin() const { return begin(); }

    auto end() const { return pre_order_iterator{}; }
    auto cend() const { return end(); }
};

template<typename T>
class pre_order_iterator { // could be nested inside BinaryTree, then the template isn't necessary
    std::stack<BinaryTree<T>::TreeNode*> to_be_visited{};

public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using reference = const value_type&;
    using pointer = const value_type*;
    using difference_type = ptrdiff_t;

    pre_order_iterator() = default;
    pre_order_iterator(BinaryTree<T>::TreeNode* root) {
        to_be_visited.push(root);
    }

    // Use default copy/move constructor/assignment and default destructor

private:
    void advance() {
        if(to_be_visited.empty()) return;

        auto node = to_be_visited.top();
        to_be_visited.pop();

        if(node->right) to_be_visited.push(node->right.get());
        if(node->left) to_be_visited.push(node->left.get());
    }

public:
    pre_order_iterator& operator++() {
        advance();
        return *this;
    }

    pre_order_iterator operator++(int) {
        auto copy = *this;
        advance();
        return copy;
    }

    reference operator*() const {
        return to_be_visited.top()->data;
    }

    pointer operator->() const {
        return &to_be_visited.top()->data;
    }

    bool operator==(const pre_order_iterator& other) const {
        if(to_be_visited.empty()) return other.to_be_visited.empty();
        if(other.to_be_visited.empty()) return false;
        return to_be_visited.top() == other.to_be_visited.top();
    }

    bool operator!=(const pre_order_iterator& other) const {
        return !(*this == other);
    }

    void swap(pre_order_iterator& other) {
        using std::swap;
        swap(to_be_visited, other.to_be_visited);
    }
};

template<typename T>
void swap(pre_order_iterator<T>& a, pre_order_iterator<T>& b) { a.swap(b); }

template <class T>
pre_order_range BinaryTree<T>::pre_order()  {
    return pre_order_range(root);
}


// usage
for(auto&& elem : tree.pre_order()) std::cout << elem << " ";

I can see the reasons for both of them, though I'd prefer the iterator approach for reusability.

Other tree operations

Insertion of new elements is covered. But what about checking whether an element is present, or removing an element? Those operations are missing.

Also, it might be worthwhile to think about balancing the tree (either automatic, or via member function call).

Implementation issues

• TreeNodes constructor accepts a T by value and then stores a copy of that in data. Using this constructor causes an unnecessary construction of a T object.

  To explain: new TreeNode{std::move(theData)} first move-constructs (in this case) a T with theData, which is then called x inside the constructor. The constructor then copy-constructs data from x. The construction of x could be avoided by providing appropriated overloads (depending on T, copies or moves might not be cheap).

• The same TreeNode constructor doesn't need to initialize left and right to nullptr.

• thisRoot in copyTree should be of type TreeNode*& (as mentioned above).

• copyTree tries to call a non-existing default constructor of TreeNode, which will fail to compile if used. I guess new TreeNode{sourceRoot->data} was meant.

• The copy constructor can be simplified to a call copyTree(root, other.root). The if expression does nothing (root would already be initialized to nullptr, and copyTree would directly return).

• Move constructor, move assignment operator and copy assignment operator call a non-existing member function swap. Calls to those member functions will fail to compile.

• In insert(T&&), the "wrong" insertPrivate member function gets called as theData doesn't get std::moved. This can be fixed by changing the call to insertPrivate(std::move(theData));.

• I don't think all the debug output (or the printXXX member functions themselves) should be part of the final interface.

• #include <iostream> is missing from the header. It works in main, because there <iostream> is included before "BinaryTree.h", but this is unreliable.

• Is it intended that inserting the same value twice will result in two TreeNodes?

• I personally don't like the swap inside the move constructor, because it causes unnecessary object constructions and assignments. Usually, if one provides a move constructor, the intention is to gain performance, not waste it.

• Using move assignment, I'd expect the moved-from BinaryTree to be empty. Guessing swap would do what is expected, the moved-from BinaryTree object would have the old state of the assignee (which would surprise me, at least).

Comments

All the comments are in best-case useless and in worst-case misleading and/or distracting.

Examples:

// Rule of 5`

This only "covers" move constructor, move assignment operator and destructor. Copy constructor is above (under // Constructors, if you will), and copy assignment is below under // Overload operators.

// These functions are for creating the tree`

No, they are for creating a node inside the tree.

// Member function

This one is more than obvious.

// Traversal functions for printing the nodes

This one is the only one midly useful, and only to highlight a flaw in design/naming. Traversal is a different concept than printing, and the member function names don't reflect that they are only intended for printing.

Internal representation

In the example code, elements 10, 8, 6, 4, 2 are inserted into a binary tree in that order. This results in the following tree:

         10
        /  \
       8
      / \
     6
    / \
   4
  / \
 2
/ \

So it's of no surprise that in-order and post-order traversal give the same result.

The recommended change in comments to change the insertion order to 8, 10, 4, 2, 6 would result in this tree:

       8
     /   \
   4       10
  / \     /  \
 2   6
/ \ / \

Advanced stuff

• Under which conditions can a BinaryTree be copied? Only if T itself is copy-constructible! This can be asserted (or better, SFINAEd) using template meta programming.

• The tree could use an emplace method to allow for in-place construction of elements.

• The insert(const T&) and insert(T&&) overloads could be disabled if T doesn't support copy- or move-construction, respectivly.

• deleteTree could be conditionally marked noexcept.

• The ordering could be taken as a template parameter (e.g. std::less<T> by default).

Answer 2

Unlike with the C language, with C++, given the STL and Boost, it is no longer practical to code an own version of a hash map or a sorting tree, unless you are squeezing the last bit of performance (even then boost::flat_map and boost::intrusive::* will most likely beat an amateur attempt in both clarity of the API and the performance).

I stopped looking further at the logic, as soon as I scanned your implementation and haven’t found anything with “rotate” in the name — when implementing a balanced binary tree, rotation abstraction naturally factors itself out, and somehow it did not happen in your implementation.

Few secondary problems:

• absence of a unit test usually results in lack of API clarity in any language, C++ is not an exception, Boost.Test or GTest are good tools to use, but a main() with consistent set of assertions may do as a “poor man’s” solution
• a sorting container would usually need to be parameterized on the sorting logic and memory management logic
• in most cases it makes sense to support the transparent comparator (see std::less<> for instance) to ensure faster lookups (for example allow searching for std::string_view in a tree of std::string

And lastly, the main piece of advice I would render to a new "C++ way" committer:

Know how to and do measure everything you are creating, only make informed choices. To get there you would typically need:

• a transparent operating system like Linux which lets you see what is going on with your application from any possible angle (strace, time, perf, /proc/pid/sched, etc.)
• a good static code analyser, I'd recommend the Clang C++ Analyzer here.
• a decent microbenchmarking rig, and CPU/memory profiling tools (perf, gprof, valgrind memcheck valgding massif) to use with it
• a basic knowledge of the assembly (a very basic one) and a convenient way of reading the assembly of the code you write (a lazy-man way is to use the godbolt or alike)

The way you use them together (for instance to answer your question about whether to use the unique_ptr or just use POD data and copy, or intern and use the pointer wrappers, like the JVM does with strings) is to compile the code with the optimizations enabled, confirm from the assembly that at least the inlining is done up to your expectations, run the tests the watch of valgrind memcheck, then valgrind massif, then benchmarks repeatedly with the microbenchmarking rig under the watch ofperf(sampling profiler) andgprof` (instrumenting profiler), removing reported errors and top N bottlenecks on each step.

If you follow the above line you are inevitably going to end up with a solution close to the optimum. And after a bit of time develop an intuition of what not to do (for example not use dynamic memory allocation of small objects in performance critical code).

How to understand if the measured numbers you see are "good enough"? You should be able to get close to number of machine instructions matching theoretical number of abstract steps needed by the algorithm, so if it is a linear search in the string of size N it should take at best N machine instructions (which translates trivially to the amount of nanoseconds for a single threaded algorithm) maybe multiplied by a factor slightly greater than 1, but not something of worse complexity caused by wrong memory management, etc.

As soon as you get bored with single threaded world ask another question, as this is the whole new topic (a one giving you the most fun on the modern hardware) :-)

Hope I could help.