void traverse(Node* root)
{
    queue<Node*> q;

    Node* temp_node= root;

    while(temp_node)
    {
        cout<<temp_node->value<<endl;

        if(temp_node->left)
            q.push(temp_node->left);

        if(temp_node->right)
            q.push(temp_node->right);

        if(!q.empty())
        {
            temp_node = q.front();
            q.pop();
        }
        else
            temp_node = NULL;
   }
 }

The above posted code is my level order traversal code. This code works fine for me but One thing I dont like is I am explicitly initializing temp_node = NULL or I use break. But it does not seem to be a good cod开发者_开发问答e to me.

Is there a neat implementation than this or how can I make this code better?

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.

Try:

void traverse(Node* root)
{
    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node* temp_node = q.front();
        q.pop();
        if (temp_node == NULL)
        {   continue;
        }

        cout << temp_node->value << endl;

        q.push(temp_node->left);
        q.push(temp_node->right);
   }
 }

I think above code snippets allow to print the level order traversal in array format. This code can help to write the solution in form of level order.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> a ; 
    vector<int> b;
    if (root == NULL)   return a;
    std::queue<TreeNode *> q;
    q.push(root);
    int nodeCount ;
    TreeNode* temp;
    while(true){
        nodeCount = q.size();
        if (nodeCount == 0)    break;
        while(!nodeCount){
            temp = q.front();
            b.push_back(temp->val);
            q.pop();
            if(temp->left != NULL)    q.push(temp->left);
            if(temp->right!= NULL)    q.push(temp->right);
            nodeCount-- ;
        }
        a.push_back(b);
        b.resize(0);
    }
    return a;
}

Output:

[ [1],
  [2,3],
  [4,5]
]

My Java solution using Queue data structure and BFS algorithm:

   void levelOrder(Node root) {
        //LinkedList is class of Queue interface
        Queue<Node> queue=new LinkedList<>(); 
        queue.add(root); 

        //Using BFS algorithm and queue used in BFS solution
        while(!queue.isEmpty()) { 
                Node node=queue.poll(); 
                System.out.print(node.data+" "); 
                if(node.left!=null) 
                queue.add(node.left); 
                if(node.right!=null) 
                queue.add(node.right); 
              }
    }

#include<iostream>
#include<queue>
using namespace std;

struct node{
   int data;
   node *left,*right;
};

// function for creating nodes of the tree dynamically...
node * new_node(int item){
   node *temp = new node();
   temp->data = item; 
   temp->left = NULL;
   temp->right = NULL;
}

//function to perform the level order tree traversal... 
void level_order(node *temp){
   queue <node*> q;              
   q.push(temp);
   while(q.empty() == false){
      temp = q.front();
      cout<<temp->data<<endl;
      if(temp->left != NULL ){
         q.push(temp->left);
      }
      if(temp->right !=NULL){
         q.push(temp->right);
      }
      q.pop();
   }
}

int main(){
  node *root = new node();       //Creating object of the structure node...
  root = NULL;
  root = new_node(4);
  root->left = new_node(3);
  root->right = new_node(2);
  root->left->left = new_node(1);
  level_order(root);              
  return 0;
}

A BST all order traversal in very simple Way

class Node():
    def __init__(self,value):
        self.value=value
        self.left_node=None
        self.right_node=None

class BTree():
    def __init__(self):
        self.root_node=None
        self.pre_order_list=[]
    def push_element(self,value):
        node=Node(value)
        if self.root_node is None:
            self.root_node=node
            return
        else:
            self.recursion_insert(value,self.root_node)

    def recursion_insert(self,value,crnt_node):
        node=Node(value)
        if node.value<crnt_node.value:
            if crnt_node.left_node is None:             
                crnt_node.left_node=node                
            elif crnt_node.left_node is not None and node.value>crnt_node.left_node.value:
                crnt_node.left_node.right_node=node             
            else:
                self.recursion_insert(value,crnt_node.left_node)
        elif node.value>crnt_node.value:
            if crnt_node.right_node is None:
                crnt_node.right_node=node
                
            elif crnt_node.right_node is not None and node.value<crnt_node.right_node.value:
                crnt_node.right_node.left_node=node
            else:
                self.recursion_insert(value,crnt_node.right_node)
        else:
            print('Duplicate Values')

    def print_preorder_traversal(self):
        self.preOrder(self.root_node)
        for i in self.pre_order_list:
            print(i,end='->')
        print('None')

    def print_inorder_traversal(self):
        self.in_order(self.root_node)

    def print_post_order_traversal(self):
        self.post_order(self.root_node)

    def print_level_order_traversal(self):
        self.level_order(self.root_node)    

    def preOrder(self,crnt_node):
        if crnt_node:
            self.pre_order_list.append(crnt_node.value)
            #print(crnt_node.value,end='->')
            self.preOrder(crnt_node.left_node)
            self.preOrder(crnt_node.right_node)
        
    def in_order(self,crnt_node):
        if crnt_node:           
            self.in_order(crnt_node.left_node)
            print(crnt_node.value,end='->')
            self.in_order(crnt_node.right_node)

    def post_order(self,crnt_node):
        if crnt_node :
            self.post_order(crnt_node.left_node)
            self.post_order(crnt_node.right_node)   
            print(crnt_node.value)

    def level_order(self,crnt_node):    
        queue_list=[]
        queue_list.append(crnt_node.value)
        while queue_list:
            if crnt_node.left_node:
                queue_list.append(crnt_node.left_node)
            if crnt_node.right_node:
                queue_list.append(crnt_node.right_node)
            queue_list.pop(0)
            print(crnt_node.value,end='->')
            if queue_list:
                crnt_node=queue_list[0]
        
tree_obj=BTree()
tree_obj.push_element(70)
tree_obj.push_element(31)
tree_obj.push_element(93)
tree_obj.push_element(34)
tree_obj.push_element(14)
tree_obj.push_element(23)
tree_obj.push_element(73)
tree_obj.push_element(94)
#tree_obj.print_preorder_traversal()
#tree_obj.print_inorder_traversal()
#tree_obj.print_post_order_traversal()
tree_obj.print_level_order_traversal()