Level Order Traversal of a Binary Tree
void traverse(Node* root)
{
queue<Node*> q;
if (root) {
q.push(root);
}
while (!q.empty())
{
const Node * const temp_node = q.front();
q.pop();
cout<<temp_node->value<<"\n";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
There, no more special case. And the indentation is cleaned up so it can be understood more easily.
Alternatively:
void traverse(Node* root)
{
queue<Node*> q;
if (!root) {
return;
}
for (q.push(root); !q.empty(); q.pop()) {
const Node * const temp_node = q.front();
cout<<temp_node->value<<"\n";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
Done up as a for
loop. Personally, I like the extra variable. The variable name is a nicer shorthand than saying 'q.front()` all the time.
You can try this way:
struct Node
{
char data;
Node* left;
Node* right;
};
void LevelOrder(Node* root)
{
if(root == NULL) return;
queue<Node*> Q;
Q.push(root);
while(!Q.empty())
{
Node* current = Q.front();
cout<< current->data << " ";
if(current->left != NULL) Q.push(current->left);
if(current->right != NULL) Q.push(current->right);
Q.pop();
}
}
One serious problem with your existing code is it crashes when it is called on an empty tree (root = NULL
).
You need to decide if you want to have NULL
pointers in the queue or not.
If not them you can only enqueue non-NULL
values.
void traverse(Node* root) {
queue<Node*> q;
// no tree no level order.
if(root == NULL) {
return;
}
// push the root to start with as we know it is not NULL.
q.push(root);
// loop till there are nodes in the queue.
while(!q.empty()) {
// dequeue the front node.
Node *tmpNode = q.front();
q.pop();
// print it..we are sure it is not NULL.
cout<<tmpNode->value<<" ";
// enqueue left child if it exists.
if(tmpNode->left) {
q.push(tmpNode->left);
}
// enqueue right child if it exists.
if(tmpNode->right) {
q.push(tmpNode->right);
}
}
}
Alternatively if you decide to have NULL
in the queue you can do:
void traverse(Node* root) {
queue<Node*> q;
// push the root..even if it is NULL.
q.push(root);
// loop till the queue is not empty.
while(!q.empty()) {
// dequeue the front node.
Node *tmpNode = q.front();
q.pop();
// the dequeued pointer can be NULL or can point to a node.
// process the node only if it is not NULL.
if(tmpNode) {
cout<<tmpNode->value<<" ";
q.push(tmpNode->left);
q.push(tmpNode->right);
}
}
}
The first method is preferred as a large tree has plenty of NULL
children (children of leaf nodes) and there is no point in having them enqueued in the queue when we later just don't process them.