Binary Search Tree Data Structure Implementation in C++11 using Smart Pointers

Question

This implementation is part of my open source project forest.

I wrote the following header file to implement a binary search tree data structure that supports the following operations:

• Insert
• Search
• Pre-Order Traversal
• In-Order Traversal
• Post-Order Traversal
• Breadth-First Traversal
• Find Minimum
• Find Maximum
• Find Predecessor
• Find Successor
• Height
• Size
• Empty

I am looking forward to hearing your opinion about this implementation and any suggestions/fixes you may have.

/**
 * @file binary_search_tree.h
 */

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
#include <memory>

/**
 * @brief The forest library namespace
 */
namespace forest {
  namespace binary_search {
    /**
     * @brief binary search Tree node struct
     */
    template <typename key_t>
    struct node {
      key_t key;     ///< The key of the node
      std::weak_ptr<node> parent;    ///< The parent of the node
      std::shared_ptr<node> left;    ///< The left child of the node
      std::shared_ptr<node> right;   ///< The right child of the node
      /**
       * @brief Constructor of a binary search tree node
       */
      node(const key_t key) {
        this->key = key;
        this->parent.reset();
        this->left = nullptr;
        this->right = nullptr;
      }
    };
    /**
     * @brief binary search tree class
     */
    template <typename key_t>
    class tree {
    private:
      std::shared_ptr<node <key_t> > root;
      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        handler(x);
        pre_order_traversal(x->left, handler);
        pre_order_traversal(x->right, handler);
      }
      void in_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        in_order_traversal(x->left, handler);
        handler(x);
        in_order_traversal(x->right, handler);
      }
      void post_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        post_order_traversal(x->left, handler);
        post_order_traversal(x->right, handler);
        handler(x);
      }
      void breadth_first_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        std::queue <std::shared_ptr<node <key_t> > > queue;
        if (x == nullptr) return;
        queue.push(x);
        while(queue.empty() == false) {
          std::shared_ptr<node <key_t> > y = queue.front();
          handler(y);
          queue.pop();
          if (y->left != nullptr) queue.push(y->left);
          if (y->right != nullptr) queue.push(y->right);
        }
      }
      const unsigned long long height(std::shared_ptr<node <key_t> > &x) {
        if (x == nullptr) return 0;
        return std::max(height(x->left), height(x->right)) + 1;
      }
      const unsigned long long size(std::shared_ptr<node <key_t> > &x) {
        if (x == nullptr) return 0;
        return size(x->left) + size(x->right) + 1;
      }
    public:
      tree() {
        root = nullptr;
      }
      ~tree() {

      }
      /**
       * @brief Performs a Pre Order Traversal starting from the root node
       * @return void
       */
      void pre_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        pre_order_traversal(root, handler);
      }
      /**
       * @brief Performs a In Order Traversal starting from the root node
       * @return void
       */
      void in_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        in_order_traversal(root, handler);
      }
      /**
       * @brief Performs a Post Order Traversal starting from the root node
       * @return void
       */
      void post_order_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        post_order_traversal(root, handler);
      }
      /**
       * @brief Performs a Breadth First Traversal starting from the root node
       * @return void
       */
      void breadth_first_traversal(void handler(std::shared_ptr<node <key_t> >)) {
        breadth_first_traversal(root, handler);
      }
      /**
       * @brief Inserts a new node into the binary search tree
       * @param key The key for the new node
       * @return The the inserted node otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > insert(const key_t key) {
        std::shared_ptr<node <key_t> > current = root;
        std::shared_ptr<node <key_t> > parent = nullptr;
        while(current!=nullptr) {
          parent = current;
          if (key > current->key) {
            current = current->right;
          } else if (key < current->key) {
            current = current->left;
          } else {
            return nullptr;
          }
        }
        current = std::make_shared<node <key_t> >(key);
        current->parent = parent;
        if(parent == nullptr) {
          root = current;
        } else if (current->key > parent->key) {
          parent->right = current;
        } else if (current->key < parent->key) {
          parent->left = current;
        }
        return current;
      }
      /**
       * @brief Performs a binary search starting from the root node
       * @return The node with the key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > search(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            return x;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the node with the minimum key
       * @return The node with the minimum key otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > minimum() {
        std::shared_ptr<node <key_t> > x = root;
        if (x == nullptr) return nullptr;
        while(x->left != nullptr) x = x->left;
        return x;
      }
      /**
       * @brief Finds the node with the maximum key
       * @return The node with the maximum key otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > maximum() {
        std::shared_ptr<node <key_t> > x = root;
        if (x == nullptr) return nullptr;
        while(x->right != nullptr) x = x->right;
        return x;
      }
      /**
       * @brief Finds the successor of the node with key specified
       * @return The successor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > successor(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->right != nullptr) {
              x = x->right;
              while(x->left != nullptr) x = x->left;
              return x;
            }
            std::shared_ptr<node <key_t> > parent = x->parent.lock();
            while (parent != nullptr && x == parent->right) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the predecessor of the node with key specified
       * @return The predecessor of the node with key specified otherwise nullptr
       */
      const std::shared_ptr<node <key_t> > predecessor(const key_t key) {
        std::shared_ptr<node <key_t> > x = root;
        while (x != nullptr) {
          if (key > x->key) {
            x = x->right;
          } else if (key < x->key) {
            x = x->left;
          } else {
            if (x->left != nullptr) {
              x = x->left;
              while(x->right != nullptr) x = x->right;
              return x;
            }
            std::shared_ptr<node <key_t> > parent = x->parent.lock();
            while (parent != nullptr && x == parent->left) {
              x = parent;
              parent = parent->parent.lock();
            }
            return parent;
          }
        }
        return nullptr;
      }
      /**
       * @brief Finds the height of the tree
       * @return The height of the binary search tree
       */
      const unsigned long long height() {
        return height(root);
      }
      /**
       * @brief Finds the size of the tree
       * @return The size of the binary search tree
       */
      const unsigned long long size() {
        return size(root);
      }
      /**
       * @brief Finds if the binary search tree is empty
       * @return true if the binary search tree is empty and false otherwise
       */
      const bool empty() {
        if (root == nullptr) {
          return true;
        } else {
          return false;
        }
      }
    };
  }
}

#endif

Here is a demonstration of how the header file above could be used.

    #include "binary_search_tree.h"

    int main() {
        // Generate a binary_search tree with integer keys
        forest::binary_search::tree <int> binary_search_tree;

        // Insert 7 plain nodes
        binary_search_tree.insert(4);
        binary_search_tree.insert(2);
        binary_search_tree.insert(90);
        binary_search_tree.insert(3);
        binary_search_tree.insert(0);
        binary_search_tree.insert(14);
        binary_search_tree.insert(45);

        // Perform In-Order-Traversal
        binary_search_tree.in_order_traversal([](auto node){ std::cout << node->key << std::endl; });

    return 0;
}

Answer 1

I would put the node inside the tree as a private member.

    template <typename key_t>
    struct node {
      key_t key;     ///< The key of the node
      std::weak_ptr<node> parent;    ///< The parent of the node
      std::shared_ptr<node> left;    ///< The left child of the node
      std::shared_ptr<node> right;   ///< The right child of the node
      /**
       * @brief Constructor of a binary search tree node
       */
      node(const key_t key) {
        this->key = key;
        this->parent.reset();
        this->left = nullptr;
        this->right = nullptr;
      }
    };

This way in the tree code it can be referenced as node rather than node<key_t>. Slightly shorter.

More importantly the node is an implementation detail that need not be exposed to the user of the tree. By exposing it you are leaking implementation details and binding your self to maintaining it.

Side note on naming. User defined types usually start with an upper case letter. While variables and functions start with a lower case letter. In C++ were types are exceedingly important information it allows you to quickly visually identify a type and thus understand the meaning of the code quicker.

I don't see the need for a parent member. It just makes things more complex.

Why are you using std::shared_ptr? Does the node own it's left and right children. What other object owns a node other than its parent? Seems like a bad choice in my opinion and you could simplify your code by using std::unique_ptr.

In all your traversals you have a handler function to do the work on each node.

      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >));

But why does the handler node get a shared_ptr by value. Why did you not pass a shared pointer by reference? Why does it even get a shared pointer? The handler should not be able to modify the tree (as it may break the constraints on the tree). In my opinion the only thing a handler can get is the data object and only a const reference to that data object.

      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(key_t const&));

Not sure why you specify a function. The problem is that a lot of code in C++11/C++14/C++17 uses lambdas (which are functors (probably)). So your handler should be a template that allows any generalized code to be executed.

      // Unchecked syntax here.
      // You may need to tweak but it will be similar to this.
      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, std::function<void(key_t)>&);

Don't define methods you don't need.

      tree() {
        root = nullptr;
      }
      ~tree() {

      }

Your member root handles all this automatically. You don't need to define a constructor.

Prefer not to be pass objects by value.

      const std::shared_ptr<node <key_t> > insert(const key_t key) {

If key_t is large then you are forcing an unneccasery copy of an expensive to copy object. Pass by const reference or r-value reference.

      const std::shared_ptr<node <key_t> > insert(key_t const& key) {
      const std::shared_ptr<node <key_t> > insert(key_t&& key) {

Why are you returning a shared_ptr? Maybe a bool to indicate successes. But returning a node allows other people to much around in the tree and invalidate the constraints on the tree. You should be guarding against this accesses not promoting it.

This is common to a lot of your functions. I would argue that returning a node and giving access to the internals of the tree is just wrong. You are allowing other peoples code to manipulate the internal consistency of your data and thus invalidate all your constraints.

If you want to give accesses to the tree have an iterator (the only need to have a parent pointer in the node).

This can be simplified.

      const bool empty() {
        if (root == nullptr) {
          return true;
        } else {
          return false;
        }
      }

You don't need a test for a boolean condition to branch the code to return a boolean value. Simply return the expression.

      const bool empty() const {  // const method.
        return (root == nullptr);
      }

Also note this function (and height/size) etc don't modify the internal structure of the tree. As a result they should be marked const.

Answer 2

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

Prefer to use token names that have some degree of uniqueness to them. Simply reusing the filename for the header guard may result in a high chance of collisions among preprocessor tokens. You can use:

• Project Name
• Namespace Name
• File name
• Any Good Differentiator - GUID / Creation Date / Random Number

Example:

//      LIB   NS     FILE                 DATE
#ifndef MYLIB_FOREST_BINARY_SEARCH_TREE_H_04042018
#define MYLIB_FOREST_BINARY_SEARCH_TREE_H_04042018

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
#include <memory>

Try to keep your #includes ordered. Especially when you get into larger projects, it's easier for the maintainers of your code to binary/dictionary search through your list compare to linear searching.

---

template <typename key_t>
struct node { ... };

Don't expose implementation details. node is an implementation detail of tree. There isn't any reason library users should know how you implemented your Binary Search Tree (BST).

    template <typename key_t>
    class tree {
    private:
      struct node { ... };

---

      std::weak_ptr<node> parent;    ///< The parent of the node
      std::shared_ptr<node> left;    ///< The left child of the node
      std::shared_ptr<node> right;   ///< The right child of the node

Is std::shared_ptr the natural ownership abstraction for your tree? Every node in your tree is owned by one other node (or is the root), so std::shared_ptr is overkill compared to std::unique_ptr. If you want to reference your parent, there is nothing wrong with using raw pointers in non-ownership contexts. C++17 will provide the world's dumbest smart pointer if you really want to avoid raw pointers.

      node * parent;                 ///< The parent of the node
      std::unique_ptr<node> left;    ///< The left child of the node
      std::unique_ptr<node> right;   ///< The right child of the node

---

      node(const key_t key) {
        this->key = key;
        this->parent.reset();
        this->left = nullptr;
        this->right = nullptr;
      }

Prefer initialization to assignment in constructors. Some class types cannot be assigned; some cannot be default-initialized, some might be expensive to assign instead of initializing.

      node(const key_t key)
      : key(key),
        parent{nullptr},
        left{nullptr},
        right{nullptr} {
      }

Since those members are initialized to constants, you can go a step further and use in-class initializers. In-class initializers make it explicit that the same value is expected to be used in all constructors while avoiding repetition.

      node * parent {nullptr};              
      std::unique_ptr<node> left {nullptr}; 
      std::unique_ptr<node> right {nullptr};

      explicit node(const key_t key) : key {key} {}

---

namespace forest {
  namespace binary_search {
    template <typename key_t>
    class tree { ... }

Naming is important. When users of your library encounter your code, can they tell what it does? There are many tree types. tree doesn't provide the type of tree it is unless its qualified by its namespace. That could be using declared away by others. Instead, doesn't it make more sense to name the class binary_search_tree? Make working with your library code easier for readers and writers.

---

      void pre_order_traversal(std::shared_ptr<node <key_t> > &x, void handler(std::shared_ptr<node <key_t> >)) {
        if (x == nullptr) return;
        handler(x);
        pre_order_traversal(x->left, handler);
        pre_order_traversal(x->right, handler);
      }

Don't pass a smart pointer as a function parameter unless you want to use or manipulate the smart pointer itself (i.e. share/transfer ownership). See GOTW 91

Make empty and single-line statements visible.

        if (x == nullptr) {
          return;
        }

---

    const std::shared_ptr<node <key_t> > insert(const key_t key) {

For input parameters, pass types that cheap to copy by value and everything else by reference to const. We don't know which key_t the user plans to use, could be an int, could be std::string.

Does the callee need to own the inserted node? The standard library returns a pair that tells the caller if it already existed and an iterator pointing to where it exists or was inserted. If you want to hand out a strong reference, consider using std::shared_ptrs aliasing constructor (see #8) to return the key_t instead of the entire node.

---

Consider the callsite readability. Why should users of your library be concerned with the details of node? Wouldn't it be better to just pass the value directly to the function being mapped?

        handler(x->key);

At the callsite, the user is only concerned with the value.

    binary_search_tree.in_order_traversal([](auto key){ std::cout << key << std::endl; });

---

      ~tree() {

      }

Since destructors are recursive by default, the destructor of your tree essentially does the following:

      ~tree() {
        // destroy root here
        // which calls root->~node()
        // which calls root->left->~node()
        // which calls root->left->left->~node()
        // which calls root->left->left->left->~node()
        // which calls root->left->left->left->left->~node()
        // ...
      }

Ignoring the fact that you allow internal nodes to have shared ownership externally, consider the worst case situation with your implementation: The tree contains \$n\$ elements, ordered, with a breadth of \$1\$ (essentially a linked-list). Everything is fine if you have enough stack space for all these recursive destructor calls. Since your stack depth isn't bounded, you'll need to provide an iterative approach to destroying the tree.

Also consider how the copy operations work with smart pointers. std::shared_ptr is copyable, but the default copy operations simply shares ownership (shallow copy) instead of creating a separately owned object (deep copy). std::unique_ptr is not copyable. To get the correct behavior for copying a tree, you will need to implement these special members yourself.

So you need a user-defined destructor, copy constructor, and copy assignment operator. According to the rule of five, if you need any of the special member functions, you should consider them all and explicitly define them (=default, =delete, or user-defined).

      ~tree() {...}                             // user-defined dtor
      tree(const tree& other) {...}             // user-defined copy ctor
      tree& operator=(const tree& other) {...}  // user-defined copy assign

      tree(const tree&) = default;              // is the compiler generated
      tree(tree&&) = default;                   // good enough?