level order trasversal of binary tree

 in binary tree is traversed level-wise starting from the first to last level sequentially.

                                                         

Algorithm: The Level Order Traversal can be implemented efficiently using a Queue.

*Create an empty queue q.

*Push the root node of tree to q. That is, q.push(root).

*Loop while the queue is not empty:

         Pop the top node from queue and print the node.

         Enqueue node's children (first left then right children) to q

         Repeat the process until queue is not empty.

c++:

void printLevelOrder(Node *root) 
{ 
    // Base Case 
    if (root == NULL) return; 

    // Create an empty queue for 
    // level order tarversal 
    queue<Node *> q; 

    // Enqueue Root and initialize height 
    q.push(root); 

    while (q.empty() == false) 
    { 
        // Print front of queue and remove 
        // it from queue 
        Node *node = q.front(); 
        cout << node->data << " "; 
        q.pop(); 

        /* Enqueue left child */
        if (node->left != NULL) 
            q.push(node->left); 

        /* Enqueue right child */
        if (node->right != NULL) 
            q.push(node->right); 
    } 
} 

java:

   void printLevelOrder() 
    { 
        Queue<Node> queue = new LinkedList<Node>(); 
        queue.add(root); 
        while (!queue.isEmpty()) 
        { 
            Node tempNode = queue.poll(); 
            System.out.print(tempNode.data + " "); 

            /* Enqueue left child */
            if (tempNode.left != null) { 
                queue.add(tempNode.left); 
            } 

            /* Enqueue right child */
            if (tempNode.right != null) { 
                queue.add(tempNode.right); 
            } 
        } 
    } 

Time Complexity: O(N), where N is the number of nodes in the Tree.

Auxiliary Space: O(N)