Level order tree traversal

Tree traversal using level order tree traversal

In Level-Order tree traversal, the data in the nodes is accessed level-wise from the top i.e from root level all the way down to the bottom of the tree.

The idea behind the level order tree traversal is as below


Algorithm : Level-Order traversal
1.    Create two queues / lists; one for storing the parent and the other for storing the children.
2.    Push the root node into the parent queue.
3.    While the parent queue or the child queue is not empty do the below
4.         While the parent queue is not empty
5.             Pop-out node P from the parent queue and print it.
6.             If node P has children, add it to the queue for children.
7.         While the child queue is not empty
8.             Pop-out node C from the child queue and print it.
9.             If node C has children, add it to the queue for the parent.


Level_Order_Traversal

Example of level-order tree traversal
Consider the level-order tree traversal for the above tree
Step 1: Node 9 being the root, it gets pushed into the Parent Queue i.e PQ [ 9 ].
Step 2: Since the Parent Queue PQ [ 9 ] is not empty, pop out the node 9 and print it.
Step 3: As the node 9 has children 5 and 16, add them to the Child Queue CQ [ 5, 16 ].
Step 4: Since the Child Queue CQ [ 5, 16 ] is not empty, pop out node 5 and print it.
            As the node 5 has children 3 and 7, add them to the Parent Queue PQ [ 3, 7 ].
            Pop out the second node 16 from the Child Queue and print it.
            As the node 16 has children 12 and 18, add them to the Parent Queue PQ [ 3, 7, 12, 18 ].

From the above it is easy to see that node 9 gets accessed first in Step 2, its children 5 and 16 get accessed in Step 4 and so on.

Level order traversals
Level 0 : 9
Level 1 : 5 16
Level 2 : 3 7 12 18
Level 3 : 6 8 25
Level 4 : 20 36

Data structure used for level-order traversals : Queue
Time Complexity of level-order traversal : O(n), where n is the number of nodes in the tree. As the push O(1) and pop O(1) operations happen only once for every node in the tree the time complexity is O(n).


C++ : Level Order tree traversal implementation using queues in C++11

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

class Node {
public:
    Node(int n) : data(n), left(NULL), right(NULL) {
    }
    Node * left;
    Node * right;
    int data;
};

void LevelOrderTreeTraversal (Node * root) {

    if(root == NULL)
       return;
    queue<Node *> parent_queue, child_queue;

    parent_queue.push(root);

    // Level 0 corresponds to the top of the tree i.e at the root level
    int level = 0;

    while (!parent_queue.empty() or !child_queue.empty()) {

        if (!parent_queue.empty())
            cout << "Level " << level << ": ";

        while (!parent_queue.empty()) {
            Node * node = parent_queue.front();
            parent_queue.pop();
            cout << node->data << " ";

            if (node->left != NULL)
                child_queue.push(node->left);
            if (node->right != NULL)
                child_queue.push(node->right);
        }
        cout << endl;
        level++;

        if (!child_queue.empty())
            cout << "Level " << level << ": ";

        while (!child_queue.empty()) {
            Node * node = child_queue.front();
            child_queue.pop();
            cout << node->data << " ";

            if (node->left != NULL)
                parent_queue.push(node->left);
            if (node->right != NULL)
                parent_queue.push(node->right);
        }
        cout << endl;
        level++;
    }
}

int main() {

/* Constructed binary tree is
               9
             /   \
            5     16
          /  \   /  \
         3   7  12   18
            / \       \
           6   8      25
                     /  \
                    20  36
*/
    Node *root = new Node(9);
    root->left = new Node(5);
    root->right = new Node(16);
    root->left->left  = new Node(3);
    root->left->right = new Node(7);
    root->left->right->left = new Node(6);
    root->left->right->right = new Node(8);
    root->right->left = new Node(12);
    root->right->right = new Node(18);
    root->right->right->right = new Node(25);
    root->right->right->right->left = new Node(20);
    root->right->right->right->right = new Node(36);

    LevelOrderTreeTraversal(root);

    // Cleanup
    delete root->right->right->right->right;
    delete root->right->right->right->left;
    delete root->right->right->right;
    delete root->right->right;
    delete root->right->left;
    delete root->left->right->right;
    delete root->left->right->left;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Output of Level-Order tree traversal

Level 0: 9 
Level 1: 5 16 
Level 2: 3 7 12 18 
Level 3: 6 8 25 
Level 4: 20 36 

Copyright (c) 2019, Algotree.org.
All rights reserved.