Binary tree traversal algorithms

Question

I recently started learning binary tree. Following is the code for a typical node for a tree (no code review required for that):

typedef unsigned int uint;

template<typename T>
class BinaryNode
{
  T t_Data;
  BinaryNode *pt_Left, *pt_Right;

public:
  BinaryNode (const T &data) : t_Data(data), pt_Left(0), pt_Right(0) {}

  void Insert (const T &data)
  {
    if(this->t_Data == data)
      return;

    BinaryNode<T> *&pNode = (data < this->t_Data)? this->pt_Left : this->pt_Right;
    if(pNode == 0)  pNode = new BinaryNode<T>(data);
    else  pNode->Insert(data);
  }

  template<uint SIZE>
  static
  BinaryNode<T>* GenerateTree (const T (&arr)[SIZE])
  {
    return GenerateTree(arr, SIZE);
  }
  static
  BinaryNode<T>* GenerateTree (const T *arr, const uint SIZE)
  {
    BinaryNode<T> *pHead = new BinaryNode<T>(arr[0]);
    for(uint i = 0; i < SIZE; i++)
      pHead->Insert(arr[i]);
    return pHead;
  }

  operator const T& () const { return t_Data; }
  BinaryNode* const getLeft () const { return pt_Left; }
  BinaryNode* const getRight () const { return pt_Right; }
};

For example to populate this tree with char nodes, one need to call the Generate function as,

const char letters[] = {'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'I', 'H'};
BinaryNode<char> *pHead = BinaryNode<char>::GenerateTree(letters);

Question: I wanted to implement, its pre-order, in-order, post-order traversals in recursive as iterative manner. We pass a traversing vector<> vTraversal to all functions to populate the traversal results.

Recursive is very simple:

template<typename T>
void PreOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  vTraverse.push_back(*pNode);
  PreOrderRecursive(pNode->getLeft(), vTraverse);
  PreOrderRecursive(pNode->getRight(), vTraverse);
}

template<typename T>
void InOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  InOrderRecursive(pNode->getLeft(), vTraverse);
  vTraverse.push_back(*pNode);
  InOrderRecursive(pNode->getRight(), vTraverse);
}

template<typename T>
void PostOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  PostOrderRecursive(pNode->getLeft(), vTraverse);
  PostOrderRecursive(pNode->getRight(), vTraverse);
  vTraverse.push_back(*pNode);
}

You can see the recursive functions are easily understandable and can relate to each other.

However, in iterative functions, I have a problem. I am able to find a good solution for pre-order traversal, a little complex solution for in-order traversal and no elegant solution for post-order traversal:

template<typename T>
void PreOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
  vector<const BinaryNode<T>*> record;
  record.push_back(pNode);
  while(record.size() != 0)
  {
    const BinaryNode<T> *pN = record.back();
    record.pop_back();
    if(pN == 0)
      continue;
    record.push_back(pN->getRight());
    record.push_back(pN->getLeft());
    vTraversal.push_back(*pN);
  }
}

template<typename T>
void InOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
  vector<const BinaryNode<T>*> record;
  record.push_back(pNode);
  while(true)
  {
    const BinaryNode<T> *pN = record.back();
    record.pop_back();
    if(pN == 0)
    {
      if(record.size() == 0)
        break;
      vTraversal.push_back(*record.back());
      record.pop_back();
      continue;
    }
    record.push_back(pN->getRight());
    record.push_back(pN);
    record.push_back(pN->getLeft());
  }
}

template<typename T>
void PostOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
   // :(
}

Is there a way by which I can make all 3 iterative solution relating to each other in the same way as recursive traversal ?

Answer 1

Did you mean to make this private?

class BinaryNode
{
public:
  T t_Data;
  BinaryNode *pt_Left, *pt_Right;

I'm not sure I agree with the interface design presented for this data structure. If you're doing this as just a practice exercise I suppose it's probably okay. However, if you're planning to reuse this in production code or real-world projects it's a good idea to follow the same interface design as the stl for consistency. In particular, you don't want client code to be able to manipulate those binary nodes since those are just implementation details.

To better separate the concerns, one idea you can try is to define an outer structure that contains a BinaryNode. Something along the lines of this:

template <typename T>
class BinaryTree
{
public:
  BinaryTree() : root(0) {}
  // rest of your interface methods here
  // Insert, GenerateTree etc.
  // ...

private:
  struct BinaryNode
  {
    T data;
    BinaryNode *left, *right;
    void Insert(const T &data_);
  };  
  BinaryNode *root;
};

---

For your GenerateTree method, it's better if you have it take iterators instead so it works with other containers besides raw arrays. It only requires a minor change to GenerateTree:

template <typename FORWARD>
static BinaryNode<T>* GenerateTree (FORWARD begin, const FORWARD &end)
{
  if(begin == end) return;

  BinaryNode<T> *pHead = new BinaryNode<T>(*begin);
  while(++begin != end)
  {
    pHead->Insert(*begin);
  }
  return pHead;
}

You can even take this a step further by providing a constructor that directly accepts iterators. Then your example usage would look like:

const char letters[] = {'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'I', 'H'};
size_t size = sizeof(letters);
BinaryTree<char> letter_tree(letters, letters + size);

---

Your PreOrderIterative function uses std::vector as a stack. Why not refactor it to use std::stack directly and improve readability?

void PreOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
  stack<const BinaryNode<T>*> record;
  record.push(pNode);
  while( !record.empty() )
  {
    const BinaryNode<T> *pN = record.top();
    record.pop();

    if(pN->getRight()) record.push(pN->getRight());
    if(pN->getLeft()) record.push(pN->getLeft());
    vTraversal.push_back(*pN);
  }
}

I haven't looked at InOrderIterative in too much detail but I'd imagine a similar refactor can be applied to it as well. I'll leave it as an exercise for you.

For PostOrderRecursive, it looks like you want to visit the nodes in this order:

     7
   /   \
  3     6
 / \   / \
1   2 4   5

One way to do this iteratively is to start at the root and as you 'walk' the tree expand its right node first then expand the left node afterwards. You can keep track of which nodes to visit with a stack similar to PreOrderIterative. As you visit each node you'll add it to vTraversal. Once done vTraversal will contain the correct order except in reverse. Apply std::reverse to get the final result:

template<typename T>
void PostOrderIterative (const BinaryNode<T>* const root, vector<T> &vTraversal)
{
  if(!root) return;

  //start with the root
  stack<const BinaryNode<T>*> visit_nodes;
  visit_nodes.push(root);
  while( !visit_nodes.empty() )
  {
    // visting the node on top of stack
    const BinaryNode<T> *curr_node = visit_nodes.top();
    vTraversal.push_back(*curr_node);
    visit_nodes.pop();

    // add nodes that still need to be visited and expand.
    // right needs to be handled before left so push in reverse order.
    if( curr_node->getLeft() ) visit_nodes.push(curr_node->getLeft());
    if( curr_node->getRight() ) visit_nodes.push(curr_node->getRight());
  }

  // vTraveral contains the desired order but in reverse.
  std::reverse(vTraversal.begin(), vTraversal.end());
}