Binary Search Tree in C++

Question

I have written this code for Binary Search tree. Help me to improve this code using C++11 and C++14. Where to use functions like minimum() maximum() predecessor() successor() insertValue(Args&&.. args)

#include <iostream>
#include <algorithm>

template<typename T>
class BinaryTree
{
  struct Node
  {
    T data;
    Node* parent;
    Node* leftChild;
    Node* rightChild;
    Node(T const& value) : data(value),
                           parent(nullptr),
                           leftChild(nullptr),
                           rightChild(nullptr)
                           {}
    //move constructor
    //It  moves the content of 'value' into the node
    Node(T&& value) : data(std::move(value)),
                      parent(nullptr),
                      leftChild(nullptr),
                      rightChild(nullptr)
                      {}
    //to enter any number and type of arguments
    template<typename... Args>
    Node(Args&&... args) : data(std::forward<Args>(args)...),
                           parent(nullptr),
                           leftChild(nullptr),
                           rightChild(nullptr)
                           {}

    ~Node()
    {
      delete leftChild;
      delete rightChild;
    }
  };

public:
  Node* root;
  BinaryTree() : root(nullptr) {}
  BinaryTree(BinaryTree const&)            = delete;
  BinaryTree& operator=(BinaryTree const&) = delete;
  ~BinaryTree()
  {
    delete root;
  }

  bool isEmpty() const
  {
    return root == nullptr;
  }

  void insertValue(T const& value)
  {
    Node* node = new Node(value);
    Node* tmp;
    node->leftChild = nullptr;
    node->rightChild = nullptr;
    node->parent = nullptr;

    if(isEmpty())
    {
      root = node;
      return;
    }
    else
    {
      Node* current = root;
      while(current)
      {
        tmp = current;
        if(node->data > current->data)
          current = current->rightChild;
        else current = current->leftChild;
      }

      if(node->data < tmp->data)
        tmp->leftChild = node;
      else tmp->rightChild = node;

      node->parent = tmp;
    }
  }

  void insertValue(T&& value)
  {
    Node* node = new Node(std::move(value));
    Node* tmp;
    node->leftChild = nullptr;
    node->rightChild = nullptr;
    node->parent = nullptr;

    if(isEmpty())
    {
       root = node;
       return;
    }
    else
    {
      Node* current = root;
      while(current)
      {
        tmp = current;
        if(node->data > current->data)
          current = current->rightChild;
        else current = current->leftChild;
      }

      if(node->data < tmp->data)
        tmp->leftChild = node;
      else tmp->rightChild = node;

      node->parent = tmp;
    }
  }

  template<typename... Args>
  void insertValue(Args&&... args)
  {
    Node* tmp;
    Node* node = new Node(std::forward<Args>(args)...);
    node->leftChild = nullptr;
    node->rightChild = nullptr;
    node->parent = nullptr;

    if(isEmpty())
    {
      root = node;
      return;
    }
    else
    {
      Node* current = root;
      while(current)
      {
        tmp = current;
        if(node->data > current->data)
          current = current->rightChild;
        else current = current->leftChild;
      }

      if(node->data < tmp->data)
        tmp->leftChild = node;
      else tmp->rightChild = node;

      node->parent = tmp;
    }
  }

    void deleteValue(T value, Node* node)
    {
      if(!node)
        return;
      if(node->data < value)
        deleteValue(value, node->rightChild);
      else if(node->data > value)
        deleteValue(value, node->leftChild);
      else
      {
        if(node->leftChild == nullptr && node->rightChild == nullptr)
        {
          if(node->parent == nullptr)
          {
            root = nullptr;
            delete node;
            return;
          }
          else if(node->parent->leftChild  == node)
          {
            node->parent->leftChild = nullptr;
            delete node;
            return;
          }
          else
          {
            node->parent->rightChild = nullptr;
            delete node;
            return;
          }
        }

        if(node->rightChild != nullptr)
        {
          T temp = node->data;
          node->data = node->rightChild->data;
          node->rightChild->data = temp;
          deleteValue(value, node->rightChild);
          return;
        }
        if(node->leftChild != nullptr)
        {
          T temp = node->data;
          node->data = node->leftChild->data;
          node->leftChild->data = temp;
          deleteValue(value, node->leftChild);
          return;
        }
      }
    }

    void deleteValue(T value)
    {
      deleteValue(value, root);
    }
    void inOrder(Node* node)
    {
      if(node != nullptr)
      {
        inOrder(node->leftChild);
        std::cout << " " << node->data;
        inOrder(node->rightChild);
      }
      else return;
    }

    void preOrder(Node* node)
    {
      if(node != nullptr)
      {
        std::cout << " " << node->data;
        if(node->leftChild) preOrder(node->leftChild);
        if(node->rightChild) preOrder(node->rightChild);
      }
      else return;
    }

    void postOrder(Node* node)
    {
      if(node != nullptr)
      {
        if(node->leftChild) postOrder(node->leftChild);
        if(node->rightChild) postOrder(node->rightChild);
        std::cout << " " << node->data;
      }
      else return;
    }

  void print_inOrder()
  {
    inOrder(root);
  }

  void print_preOrder()
  {
    preOrder(root);
  }

  void print_postOrder()
  {
    postOrder(root);
  }

private:

  Node* search(Node* root, T value) const
  {
    if(root == nullptr || value == root->data)
      return root;

    if(value < root->data)
      return search(root->leftChild, value);

    else
      return search(root->rightChild, value);
  }

  Node* minimum(Node* root)
  {
      while(root->leftChild != nullptr)
          root = root->leftChild;
      return root;
  }

  Node* maximum(Node* root)
  {
      while(root->rightChild != nullptr)
          root = root->rightChild;
      return root;
  }

  //Successor - a node which has the next higher key
  Node* successor(Node* node)
  {
      if(node->rightChild != nullptr)
        return minimum(node->rightChild);

      Node* temp = node->parent;

      while(temp != nullptr && node == temp->rightChild)
      {
          node = temp;
          temp = temp->parent;
      }
      return temp;
  }

  //Predecessor - a node which has the next lower key
  Node* predecessor(Node* node)
  {
      if(node->leftChild != nullptr)
        return maximum(node->leftChild);

      Node* temp = node->parent;

      while(temp != nullptr && node == temp->leftChild)
      {
          node = temp;
          temp = temp->parent;
      }
      return temp;
  }

};

int main()
{
  BinaryTree<int> bt1;
  bt1.insertValue(100);
  bt1.insertValue(20);
  bt1.insertValue(30);
  bt1.insertValue(400);
  bt1.insertValue(50);
  std::cout << "In Order: ";
  bt1.print_inOrder();
  std::cout<<"\n";
  std::cout << "Pre Order: ";
  bt1.print_preOrder();
  std::cout<<"\n";
  std::cout << "Post Order: ";
  bt1.print_postOrder();
  std::cout << "\nDeleting 20 ";
  bt1.deleteValue(20);
  std::cout<<"\n";
  std::cout << "In Order: ";
  bt1.print_inOrder();
  std::cout<<"\n";
  std::cout << "Pre Order: ";
  bt1.print_preOrder();
  std::cout<<"\n";
  std::cout << "Post Order: ";
  bt1.print_postOrder();
}

Have you tried implementing an in order iterator for it? You could implement others too, and make a function which would return a range. You could as well make it mandatory, so that it will be obvious which kind of traversal is going on. — Incomputable, Commented Sep 24, 2017 at 19:20
Have you considered foregoing pointers in favor of std::optional<std::ref<Node>>s? It's technically C++17 but C++14 has std::experimental::optional. — einpoklum, Commented Oct 6, 2017 at 15:15

R Sahu · Accepted Answer · 2017-09-30 06:01:16Z

The other answer makes some excellent suggestions. I won't repeat them here.

You have a bug in `insertValue`

You don't have any checks to make sure that a value is not inserted twice.

If I use

bt1.insertValue(20);
bt1.insertValue(20);

insertValue gladly inserts 20 twice into the tree. A simple update to insertValue will fix that.

void insertValue(T const& value)
{
   // If the value is already there, don't insert it.
   if ( search(root, value) != nullptr )
   {
      return;
   }

   // Rest of your code.
}

Make `Node` a `private` `struct` of `BinaryTree`

Node does not need to be exposed to users of BinaryTree. It's best to make it a private struct of the class.

Don't hard code `std::cout` as the sole target to output `BinaryTree`

It will be better to provide an operator<< function to output BinaryTree.

std::ostream& operator<<(std::ostream& out, BinaryTree cons& t)
{
  // Do the needful to print t.
  return out;
}

After that, you could use:

std::cout << bt1 << std::endl;

That will also allow you to print a BinaryTree to any std::ostream.

Use manipulator in the spirit of the standard library

Instead of using

 bt1.print_preOrder();

you can use something like:

 std::cout << setprintorder(PreOrder) << bt1 << endl;

To print the a BinaryTree in "in order" and "post order" style, you can use:

 std::cout << setprintorder(InOrder) << bt1 << endl;
 std::cout << setprintorder(PostOrder) << bt1 << endl;

You will need some supporting code to pull that off.

Here's my simple attempt to support that:

enum BinaryTreePrintOrder {InOrder, PreOrder, PostOrder};
struct BinaryTreeManipulator { BinaryTreePrintOrder o; };
static BinaryTreeManipulator m;

std::ostream& operator<<(std::ostream& out, BinaryTreeManipulator )
{
   // This function does not do anything. It just allows
   // for syntactic form similar to the manipulators in the
   // standard library.
   return out;
}

BinaryTreeManipulator& setprintorder(BinaryTreePrintOrder o)
{
   m.o = o;
   return m;
}

BinaryTreePrintOrder getprintorder()
{
   return m.o;
}

and then, in the operator<< function, you can use:

friend std::ostream& operator<<(std::ostream& out, BinaryTree const& t)
{
   if ( getprintorder() == InOrder )
   {
      t.inOrder(t.root, out);
   }
   else if ( getprintorder() == PreOrder )
   {
      t.preOrder(t.root, out);
   }
   else
   {
      t.postOrder(t.root, out);
   }
   return out;
}

Make the `printXXX` functions `const` member functions

Without that the operator<< function won't work.

Here's an updated version of your program:

#include <iostream>
#include <algorithm>

enum BinaryTreePrintOrder {InOrder, PreOrder, PostOrder};
struct BinaryTreeManipulator { BinaryTreePrintOrder o; };
static BinaryTreeManipulator m;

std::ostream& operator<<(std::ostream& out, BinaryTreeManipulator )
{
   return out;
}

BinaryTreeManipulator& setprintorder(BinaryTreePrintOrder o)
{
   m.o = o;
   return m;
}

BinaryTreePrintOrder getprintorder()
{
   return m.o;
}

template<typename T>
class BinaryTree
{
   private:

      struct Node
      {
         T data;
         Node* parent;
         Node* leftChild;
         Node* rightChild;
         Node(T const& value) : data(value),
         parent(nullptr),
         leftChild(nullptr),
         rightChild(nullptr)
         {}
         //move constructor
         //It  moves the content of 'value' into the node
         Node(T&& value) : data(std::move(value)),
         parent(nullptr),
         leftChild(nullptr),
         rightChild(nullptr)
         {}
         //to enter any number and type of arguments
         template<typename... Args>
            Node(Args&&... args) : data(std::forward<Args>(args)...),
            parent(nullptr),
            leftChild(nullptr),
            rightChild(nullptr)
         {}

         ~Node()
         {
            delete leftChild;
            delete rightChild;
         }
      };

   public:
      Node* root;
      BinaryTree() : root(nullptr) {}
      BinaryTree(BinaryTree const&)            = delete;
      BinaryTree& operator=(BinaryTree const&) = delete;
      ~BinaryTree()
      {
         delete root;
      }

      bool isEmpty() const
      {
         return root == nullptr;
      }

      void insertValue(T const& value)
      {
         // If the value is already there, don't insert it.
         if ( search(root, value) != nullptr )
         {
            return;
         }

         Node* node = new Node(value);
         Node* tmp;
         node->leftChild = nullptr;
         node->rightChild = nullptr;
         node->parent = nullptr;

         if(isEmpty())
         {
            root = node;
            return;
         }
         else
         {
            Node* current = root;
            while(current)
            {
               tmp = current;
               if(node->data > current->data)
                  current = current->rightChild;
               else current = current->leftChild;
            }

            if(node->data < tmp->data)
               tmp->leftChild = node;
            else tmp->rightChild = node;

            node->parent = tmp;
         }
      }

      void insertValue(T&& value)
      {
         // If the value is already there, don't insert it.
         if ( search(root, value) != nullptr )
         {
            return;
         }

         Node* node = new Node(std::move(value));
         Node* tmp;
         node->leftChild = nullptr;
         node->rightChild = nullptr;
         node->parent = nullptr;

         if(isEmpty())
         {
            root = node;
            return;
         }
         else
         {
            Node* current = root;
            while(current)
            {
               tmp = current;
               if(node->data > current->data)
                  current = current->rightChild;
               else current = current->leftChild;
            }

            if(node->data < tmp->data)
               tmp->leftChild = node;
            else tmp->rightChild = node;

            node->parent = tmp;
         }
      }

      template<typename... Args>
         void insertValue(Args&&... args)
         {
            Node* tmp;
            Node* node = new Node(std::forward<Args>(args)...);
            node->leftChild = nullptr;
            node->rightChild = nullptr;
            node->parent = nullptr;

            if(isEmpty())
            {
               root = node;
               return;
            }
            else
            {
               Node* current = root;
               while(current)
               {
                  tmp = current;
                  if(node->data > current->data)
                     current = current->rightChild;
                  else current = current->leftChild;
               }

               if(node->data < tmp->data)
                  tmp->leftChild = node;
               else tmp->rightChild = node;

               node->parent = tmp;
            }
         }

      void deleteValue(T value, Node* node)
      {
         if(!node)
            return;
         if(node->data < value)
            deleteValue(value, node->rightChild);
         else if(node->data > value)
            deleteValue(value, node->leftChild);
         else
         {
            if(node->leftChild == nullptr && node->rightChild == nullptr)
            {
               if(node->parent == nullptr)
               {
                  root = nullptr;
                  delete node;
                  return;
               }
               else if(node->parent->leftChild  == node)
               {
                  node->parent->leftChild = nullptr;
                  delete node;
                  return;
               }
               else
               {
                  node->parent->rightChild = nullptr;
                  delete node;
                  return;
               }
            }

            if(node->rightChild != nullptr)
            {
               T temp = node->data;
               node->data = node->rightChild->data;
               node->rightChild->data = temp;
               deleteValue(value, node->rightChild);
               return;
            }
            if(node->leftChild != nullptr)
            {
               T temp = node->data;
               node->data = node->leftChild->data;
               node->leftChild->data = temp;
               deleteValue(value, node->leftChild);
               return;
            }
         }
      }

      void deleteValue(T value)
      {
         deleteValue(value, root);
      }

      friend std::ostream& operator<<(std::ostream& out, BinaryTree const& t)
      {
         if ( getprintorder() == InOrder )
         {
            t.inOrder(t.root, out);
         }
         else if ( getprintorder() == PreOrder )
         {
            t.preOrder(t.root, out);
         }
         else
         {
            t.postOrder(t.root, out);
         }

         return out;
      }


      void print_inOrder(std::ostream& out) const
      {
         inOrder(root, out);
      }

      void print_preOrder(std::ostream& out) const
      {
         preOrder(root, out);
      }

      void print_postOrder(std::ostream& out) const
      {
         postOrder(root, out);
      }

      void inOrder(Node* node, std::ostream& out) const
      {
         if(node != nullptr)
         {
            inOrder(node->leftChild, out);
            out << " " << node->data;
            inOrder(node->rightChild, out);
         }
      }

      void preOrder(Node* node, std::ostream& out) const
      {
         if(node != nullptr)
         {
            out << " " << node->data;
            if(node->leftChild) preOrder(node->leftChild, out);
            if(node->rightChild) preOrder(node->rightChild, out);
         }
      }

      void postOrder(Node* node, std::ostream& out) const
      {
         if(node != nullptr)
         {
            if(node->leftChild) postOrder(node->leftChild, out);
            if(node->rightChild) postOrder(node->rightChild, out);
            out << " " << node->data;
         }
      }

      Node* search(Node* root, T value) const
      {
         if(root == nullptr || value == root->data)
            return root;

         if(value < root->data)
            return search(root->leftChild, value);

         else
            return search(root->rightChild, value);
      }

      Node* minimum(Node* root)
      {
         while(root->leftChild != nullptr)
            root = root->leftChild;
         return root;
      }

      Node* maximum(Node* root)
      {
         while(root->rightChild != nullptr)
            root = root->rightChild;
         return root;
      }

      //Successor - a node which has the next higher key
      Node* successor(Node* node)
      {
         if(node->rightChild != nullptr)
            return minimum(node->rightChild);

         Node* temp = node->parent;

         while(temp != nullptr && node == temp->rightChild)
         {
            node = temp;
            temp = temp->parent;
         }
         return temp;
      }

      //Predecessor - a node which has the next lower key
      Node* predecessor(Node* node)
      {
         if(node->leftChild != nullptr)
            return maximum(node->leftChild);

         Node* temp = node->parent;

         while(temp != nullptr && node == temp->leftChild)
         {
            node = temp;
            temp = temp->parent;
         }
         return temp;
      }
};


int main()
{
   BinaryTree<int> bt1;
   bt1.insertValue(100);
   bt1.insertValue(20);
   bt1.insertValue(20);
   bt1.insertValue(30);
   bt1.insertValue(400);
   bt1.insertValue(50);

   std::cout << "In Order: ";
   std::cout << setprintorder(InOrder) << bt1 << std::endl;
   std::cout << "Pre Order: ";
   std::cout << setprintorder(PreOrder) << bt1 << std::endl;
   std::cout << "Post Order: ";
   std::cout << setprintorder(PostOrder) << bt1 << std::endl;

   std::cout << "Deleting 20 ";
   bt1.deleteValue(20);
   std::cout<<"\n";

   std::cout << "In Order: ";
   std::cout << setprintorder(InOrder) << bt1 << std::endl;
   std::cout << "Pre Order: ";
   std::cout << setprintorder(PreOrder) << bt1 << std::endl;
   std::cout << "Post Order: ";
   std::cout << setprintorder(PostOrder) << bt1 << std::endl;
}

and its output:

In Order:  20 30 50 100 400
Pre Order:  100 20 30 50 400
Post Order:  50 30 20 400 100
Deleting 20 
In Order:  30 50 100 400
Pre Order:  100 30 50 400
Post Order:  50 30 400 100

user1118321 · Accepted Answer · 2017-09-24 17:31:35Z

This code is very easy to read! Your naming is quite good, and it's very clear what's going on in each function. Here are some things I'd improve:

Don't Repeat Yourself

I notice in all 3 of the insertValue() methods, you're setting the newly created node's parent, and left and right children to nullptr. You've already done that in the constructor for Node, so there's no reason to also do it in insertValue(). Also, the body of each insertValue() function is identical except for the call to create the new Node. You should factor that out into a separate method.

Likewise, you have public functions for inOrder(), preOrder(), and postOrder(), but then you created wrapper methods for print_inOrder(), print_preOrder(), and print_postOrder() that literally do nothing other than call the other corresponding methods. If that's all the functionality you need, then I'd remove the print* ones and rename the other ones to print*. (Also, it's a bit odd that you're mixing both CamelCase and use of underscores in the names of print_*. Pick one or the other.)

I do think there's a valid case for having both sets of functions. That would be if the generically named ones took either a function pointer or lambda to do something to each node as it traversed the tree. Then the print_* methods could call it with a function or lambda that simply prints out the value, and they could be reused for other things if you have that need.

Don't Make Functions Private If They're Not Used

I'm unclear on what you're trying to accomplish with search(), minimum(), maximum() et al. You ask:

Where to use functions like minimum() maximum() predecessor() successor() insertValue(Args&&.. args)

That's up to you! If you think users of this class have a use for them, I'd make them public. But that's going to depend entirely on how the class will be used. I think they're potentially useful functions.

Errors

Your minimum(), maximum(), successor() and predecessor() methods don't check to see if the passed-in Node is nullptr. That can lead to a crash if they're called on an empty tree.

Early Returns

I'm not a huge fan of early returns. I think they tend to make the code harder to reason about and have the potential to introduce hard-to-detect errors. For something like deletValue(), I'd probably leave the first one for if (!node), but I'd rewrite the large chain of if statements in the last block to not need a return statement. Something like this:

void deleteValue(T value, Node* node)
{
  if(!node)
  {
    return;
  }

  if(node->data < value)
  {
    deleteValue(value, node->rightChild);
  }
  else if(node->data > value)
  {
    deleteValue(value, node->leftChild);
  }
  else if(node->leftChild == nullptr && node->rightChild == nullptr)
  {
      if(node->parent == nullptr)
      {
        root = nullptr;
        delete node;
      }
      else if(node->parent->leftChild  == node)
      {
        node->parent->leftChild = nullptr;
        delete node;
      }
      else
      {
        node->parent->rightChild = nullptr;
        delete node;
      }
  }
  else if(node->rightChild != nullptr)
  {
      T temp = node->data;
      node->data = node->rightChild->data;
      node->rightChild->data = temp;
      deleteValue(value, node->rightChild);
  }
  else if(node->leftChild != nullptr)
  {
      T temp = node->data;
      node->data = node->leftChild->data;
      node->leftChild->data = temp;
      deleteValue(value, node->leftChild);
  }
}

Nitpicks

This is something minor that doesn't really affect the running of the program, but in inOrder(), preOrder() and postOrder(), you don't need to put a return in the else clause. You can just leave off the else and the return will happen anyway.

Stack Exchange Network

Binary Search Tree in C++

2 Answers 2

You have a bug in `insertValue`

Make `Node` a `private` `struct` of `BinaryTree`

Don't hard code `std::cout` as the sole target to output `BinaryTree`

Use manipulator in the spirit of the standard library

Make the `printXXX` functions `const` member functions

Don't Repeat Yourself

Don't Make Functions Private If They're Not Used

Errors

Early Returns

Nitpicks

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
c++11
tree
binary-search
or ask your own question.

Hot Network Questions

Binary Search Tree in C++

2 Answers 2

You have a bug in insertValue

Make Node a private struct of BinaryTree

Don't hard code std::cout as the sole target to output BinaryTree

Use manipulator in the spirit of the standard library

Make the printXXX functions const member functions

Don't Repeat Yourself

Don't Make Functions Private If They're Not Used

Errors

Early Returns

Nitpicks

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++c++11treebinary-search or ask your own question.

Related

Hot Network Questions

You have a bug in `insertValue`

Make `Node` a `private` `struct` of `BinaryTree`

Don't hard code `std::cout` as the sole target to output `BinaryTree`

Make the `printXXX` functions `const` member functions

Not the answer you're looking for? Browse other questions tagged
c++
c++11
tree
binary-search
or ask your own question.