Thread: binary tree traversal

I want to traverse the binary tree breadth-first

Code:

void Tree::bf_traverse()
{
  qu_node(root);
}

void Tree::qu_node( Tree::Node* node)
{
  traverse_tree.push(node);
  if(node->relate[1] != NULL)
    {
      
      qu_node(node->relate[1]);
    }
  if(node->relate[2] != NULL)
    qu_node(node->relate[2]);
}

where traverse_tree is a queue<Node*>. I thought this will give me breadth first traversal, but it turned out to be depth-first because of the way I recurse. Is there another way to organize this to obtain level-order?

Originally Posted by tabstop

If you want bottom-to-top, wouldn't you want to push the root node on last?

tabstop, actually, I want to push all the nodes in the same level in. What I have just push the in the left child and its children in first, before the right child and its children are pushed in.

gotcha, thanks.

Found the solution :-D

Code:

void Tree::bf_traverse()
{
  qu_node(root);
}

// breadth-first tree traversal
void Tree::qu_node( Tree::Node* node)
{
  queue<Node*> temp; 
  temp.push(node);
  Tree::Node* p; 
  while( !temp.empty() )
    {
      p = temp.front();
      traverse_tree.push(p);
      
      if(p->relate[1] !=NULL)
	temp.push(p->relate[1]);
      if(p->relate[2] != NULL)
	temp.push(p->relate[2]);
      temp.pop(); 
    }
}