Breadth First Traversal of a Tree

[wpdm_package id=’1379′]

Algorithm:

  • visit the root.
  • While traversing level l, keep all the elements at level l+1 in queue.
  • Go to the next level and visit all the nodes at that level.
  • Repeat this until all levels are completed.

[sourcecode lang=”cpp”]
void LevelOrder(tree_node *r)
{ tree_node *temp;
std::queue<tree_node*> Q;
if(!r)
return;
Q.push(r);

while(!Q.empty())
{ temp=Q.front();
Q.pop();
cout<<temp->data<<" ";
if(temp->left)
{
Q.push(temp->left);
}
if(temp->right)
{
Q.push(temp->right);
}

}
}
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *