Binary tree traversal algorithms

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

  template
  static
  BinaryNode* GenerateTree (const T (&arr)[SIZE])
  {
    return GenerateTree(arr, SIZE);
  }
  static
  BinaryNode* GenerateTree (const T *arr, const uint SIZE)
  {
    BinaryNode *pHead = new BinaryNode(arr[0]);
    for(uint i = 0; i 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 *pHead = BinaryNode::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
void PreOrderRecursive (const BinaryNode* const pNode, vector &vTraverse)
{
if(pNode == 0)
return;
vTraverse.push_back(*pNode);
PreOrderRecursive(pNode->getLeft(), vTraverse);
PreOrderRecursive(pNode->getRight(), vTraverse);
}

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

temp

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 
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 
static BinaryNode* GenerateTree (FORWARD begin, const FORWARD &end)
{
  if(begin == end) return;

  BinaryNode *pHead = new BinaryNode(*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 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* const pNode, vector &vTraversal)
{
  stack*> record;
  record.push(pNode);
  while( !record.empty() )
  {
    const BinaryNode *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
void PostOrderIterative (const BinaryNode* const root, vector &vTraversal)
{
  if(!root) return;

  //start with the root
  stack*> visit_nodes;
  visit_nodes.push(root);
  while( !visit_nodes.empty() )
  {
    // visting the node on top of stack
    const BinaryNode *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());
}

StackExchange Code Review Q#6399, answer score: 4