Level Order Traversal Of A Tree In C++

January 21, 2021

Level Order Traversal Of A Tree

A tree can be traversed using level order and depth first order. In level order traversal, we move level by level that is we visit all the nodes in the same level then move onto the next level. Level order traversal can be achieved using recursion or queue.

Level order traversal of a tree in C++

Algorithm:

  1. If the root is NULL, return.
  2. Otherwise push the root in queue.
  3. Print the node’s data and add its left and right child.
  4. Pop the node from the queue.
  5. Repeat until the queue is empty.

Why Queue is better to traverse than Recursion?

  1. Queues improves the time complexity because recursion gives the time complexity of O(2^n) in the worst case, whereas queue gives time complexity of O(n).
  2. Height of the tree is first calculated to print level order but this is not required in queue.
  3. Implementation is shorter in queues.

Code:

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void level_order(Tree *root) {
    if (root == NULL) return; // Checking whether NULL
    queue<Tree *> q;
    q.push(root); // Adding root to queue
    while (!q.empty()) {
        cout << q.front() -> data << ” “; // Printing Data
        // Adding left and right child if not null
        if (q.front() -> left != NULL) {
            q.push(q.front() -> left);
        }
        if (q.front() -> right != NULL) {
            q.push(q.front() -> right);
        }
        // Removing the node from queue
        q.pop();
    }
}
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(20);
    root -> right = new Tree(30);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(50);
    level_order(root);
    return 0;
}

Output:

10 20 30 40 50

Time Complexity
For Level Order Travesal

Time Complexity

O(n)

Space Complexity

O(n)