Level-wise traversal of a binary tree

Write an Algorithm to print the elements of a binary tree in level-wise order. For example if the Binary tree is as given below:

Then the traversal should be in the following order:

Solution:

Also see The basic tree traversals(preorder, inorder & postorder)…

Have you learn about the Breadth-First search algorithm in Graph theory?

The Breadth-first search algorithm in Graph theory starts the search from the root node and move to all the adjacent nodes. If we apply this algorithm on a tree (A tree is a connected a-cyclic Graph), then, we will be traversing the tree in level-order.

Hence the answer is much simpler than it looks, Just apply the BFS algorithm on the given binary Tree.

Algorithm:

For BFS algorithm we need a Queue (First-Come-First-server data structure)

Let Q be an Empty Queue with operations enqueue, dequeue and empty. The below algorithm prints the nodes of the tree in a level-wise order.

    void printLevel(root r)
    {
        // Enqueue the root in the Queue.
        Q.enqueue(r);
        while(!Q.empty())
        {
            // Print the top element in the Queue and insert its children
            Node *temp = Q.dequeue();
            cout << temp->data;
            if(temp->left){  Q.enqueue(temp->left); }
            if(temp->right){  Q.enqueue(temp-> right); }
        }
    }

There is another way to print the nodes of the tree in level-wise using recursion and printing all the nodes at a particular height at one time, but that is very inefficient. I am not discussing that, but I know you should be able to do that.