Traversing a Binary Tree

There are basically two ways of traversing a binary tree
1. Depth First Traversals
2. Breadth First Traversal

Depth First Traversal
A binary tree can be traversed in three ways using the depth first approach namely

1. Inorder Traversal

template <typename T>
  void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      inOrder(node->left, out);
      out.push_back(node->key);
      inOrder(node->right, out);
    }
  }

2. Preorder Traversal

template <typename T>
  void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      out.push_back(node->key);
      preOrder(node->left, out);
      preOrder(node->right, out);
    }
  }

3. Postorder Traversal

template <typename T>
  void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
  {
    if(node)
    {
      postOrder(node->left, out);
      postOrder(node->right, out);
      out.push_back(node->key);
    }
  }

Breadth First Traversal
There is only one kind of Breadth first traversal viz. Level Order traversal. This traversal does not move along the branches of the tree but makes use of a FIFO queue. In the sample code, I have used std::deque as the helper queue for achieving the same.

template <typename T>
  void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
  {
    std::deque<BSTNode<T>*> hQ;
    hQ.push_back(bstree->m_root);
    levelOrder(hQ, out);
  }

  template <typename T>
  void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
  {
    while(hQ.empty() == false)
    {
      BSTNode<T> *current = hQ.front();
      if(current != NULL)
      {
        hQ.pop_front();
        out.push_back(current->key);
        addChildren(current, hQ);
      }
    }
  }

The BTTraveller class takes care of returning Binary Tree node elements in the order you are traversing the tree.

 1 #ifndef _BTTraveller_H_
 2 #define _BTTraveller_H_
 3 #include "BSTNode.h"
 4 #include <deque>
 5 
 6 //File: BTTraveller.h
 7 namespace algorithms
 8 {
 9   template <typename T>
10   class BTTraveller
11   {
12   public:
13     static void inOrder(BST<T> *bstree, std::deque<T> &elems);
14     static void preOrder(BST<T> *bstree, std::deque<T> &elems);
15     static void postOrder(BST<T> *bstree, std::deque<T> &elems);
16     static void levelOrder(BST<T> *bstree, std::deque<T> &elems);
17 
18   private:
19     static void inOrder(BSTNode<T> *node, std::deque<T> &elems);
20     static void preOrder(BSTNode<T> *node, std::deque<T> &elems);
21     static void postOrder(BSTNode<T> *node, std::deque<T> &elems);
22     static void levelOrder(std::deque<BSTNode<T>*> &helperQ, std::deque<T> &elems);
23     static void addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &helperQ);
24 
25     BTTraveller();
26     BTTraveller(const BTTraveller&);
27     const BTTraveller& operator=(const BTTraveller&);
28   };
29 };
30 
31 #include "BTTraveller.hpp"
32 #endif //_BTTraveller_H_

 1 //File: BTTraveller.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   void BTTraveller<T>::inOrder(BST<T> *bstree, std::deque<T> &out)
 6   {
 7     inOrder(bstree->m_root, out);
 8   }
 9 
10   template <typename T>
11   void BTTraveller<T>::preOrder(BST<T> *bstree, std::deque<T> &out)
12   {
13     preOrder(bstree->m_root, out);
14   }
15 
16   template <typename T>
17   void BTTraveller<T>::postOrder(BST<T> *bstree, std::deque<T> &out)
18   {
19     postOrder(bstree->m_root, out);
20   }
21 
22   template <typename T>
23   void BTTraveller<T>::levelOrder(BST<T> *bstree, std::deque<T> &out)
24   {
25     std::deque<BSTNode<T>*> hQ;
26     hQ.push_back(bstree->m_root);
27     levelOrder(hQ, out);
28   }
29 
30   template <typename T>
31   void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out)
32   {
33     if(node)
34     {
35       inOrder(node->left, out);
36       out.push_back(node->key);
37       inOrder(node->right, out);
38     }
39   }
40 
41   template <typename T>
42   void BTTraveller<T>::preOrder(BSTNode<T> *node, std::deque<T> &out)
43   {
44     if(node)
45     {
46       out.push_back(node->key);
47       preOrder(node->left, out);
48       preOrder(node->right, out);
49     }
50   }
51 
52   template <typename T>
53   void BTTraveller<T>::postOrder(BSTNode<T> *node, std::deque<T> &out)
54   {
55     if(node)
56     {
57       postOrder(node->left, out);
58       postOrder(node->right, out);
59       out.push_back(node->key);
60     }
61   }
62 
63   template <typename T>
64   void BTTraveller<T>::levelOrder(std::deque<BSTNode<T>*> &hQ, std::deque<T> &out)
65   {
66     while(hQ.empty() == false)
67     {
68       BSTNode<T> *current = hQ.front();
69       if(current != NULL)
70       {
71         hQ.pop_front();
72         out.push_back(current->key);
73         addChildren(current, hQ);
74       }
75     }
76   }
77 
78   template <typename T>
79   void BTTraveller<T>::addChildren(BSTNode<T> *node, std::deque<BSTNode<T>*> &hQ)
80   {
81     if(node->left != NULL)
82     {
83       hQ.push_back(node->left);
84     }
85     if(node->right != NULL)
86     {
87       hQ.push_back(node->right);
88     }
89   }
90 }

You need to include BTTraveller class as a friend class in both the BSTNode as well as BST class declarations. This ensures that the BTTraveller class has access to private data members of these two classes

The BSTNode class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BTTraveller;
13 
14   template <typename T>
15   class BSTNode
16   {
17   public:
18     BSTNode(T key);
19     ~BSTNode();
20 
21     friend class BST<T>;
22     friend class BTTraveller<T>;
23 
24   private:
25     BSTNode<T> *left;
26     BSTNode<T> *right;
27     T key;
28   };
29 };
30 
31 #include "BSTNode.hpp"
32 #endif //_BSTNode_H_

The BST class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BTTraveller;
10 
11   template <typename T>
12   class BST
13   {
14   public:
15     BST();
16     ~BST();
17 
18     //modifiers
19     void insert(T key);
20     void remove(T key);
21     void clear();
22 
23     //accessors
24     bool find(T key);
25     bool isEmpty() const;
26 
27     friend class BTTraveller<T>;
28 
29   private:
30     void remove(BSTNode<T> **node);
31     void clear(BSTNode<T> *node);
32     BSTNode<T>** find(BSTNode<T> **node, const T key);
33     BSTNode<T>** getSuccessor(BSTNode<T> **node);
34     BSTNode<T>* getNewNode(T key);
35 
36     //instance fields
37     BSTNode<T> *m_root;
38   };
39 };
40 
41 #include "BST.hpp"
42 #endif //_BinarySearchTree_H_

The BSTNode.hpp and BST.hpp files remains the same as in the post
The Client Program

 1 #include "BST.h"
 2 #include "BTTraveller.h"
 3 #define MAX 20
 4 using namespace algorithms;
 5 
 6 //File: Main.cpp
 7 
 8 template <typename T>
 9 void DumpDeque(std::deque<T> &q)
10 {
11   std::cout << std::endl;
12   std::deque<T>::const_iterator itr;
13   for(itr = q.cbegin(); itr != q.cend(); ++itr)
14   {
15     std::cout << *itr << " ";
16   }
17   std::cout << std::endl;
18   q.clear();
19 }
20 
21 int main(int argc, char *argv[])
22 {
23   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120, 111 };
24   BST<int> bstInt;
25   for(int i = 0; i < MAX; ++i)
26   {
27     bstInt.insert(nodes[i]);
28   }
29 
30   std::deque<int> elems;
31   BTTraveller<int>::inOrder(&bstInt, elems);
32   DumpDeque(elems);
33   BTTraveller<int>::preOrder(&bstInt, elems);
34   DumpDeque(elems);
35   BTTraveller<int>::postOrder(&bstInt, elems);
36   DumpDeque(elems);
37   BTTraveller<int>::levelOrder(&bstInt, elems);
38   DumpDeque(elems);
39 
40   return 0;
41 }

Output

$ ./BinarySearchTree.exe

1 5 10 15 20 30 35 40 50 60 65 70 75 80 90 100 110 111 120 130

50 40 20 10 5 1 15 30 35 60 70 65 80 75 90 100 110 130 120 111

1 5 15 10 35 30 20 40 65 75 111 120 130 110 100 90 80 70 60 50

50 40 60 20 70 10 30 65 80 5 15 35 75 90 1 100 110 130 120 111