How to Perform Level Order Traversal?

Introduction

In this article, we will be learning the level order traversal. This is one of the most important topics to traverse graphs. You will be given a root of the tree and then you have to print its level order traversal.

There are two methods to traverse a tree using level order. We will be learning both methods in this article:

Method 1: Using Recursion

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node *left, *right;
};
node* newNode(int data);
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

int height(node* node) {
    if (node == NULL)
        return 0;
    else {
        int lheight = height(node->left);
        int rheight = height(node->right);
        if (lheight > rheight) {
            return(lheight + 1);
        }
        else {
          return(rheight + 1);
        }
    }
}

void CurrentLevel(node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
      CurrentLevel(root->left, level-1);
      CurrentLevel(root->right, level-1);
    }
}

void LevelOrder(node* root) {
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++)
    CurrentLevel(root, i);
}



int main() {
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    LevelOrder(root);
    return 0;
}

write your code here: Coding Playground

Time Complexity: O(N2), where N is the number of nodes in the skewed tree. So the time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(N2).

Auxiliary Space:  O(N) in the worst case. For a skewed tree, printGivenLevel() uses O(n) space for the call stack. For a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).

Method 2: Using Queue

  • Create an empty queue q and push root in q.
  • Run While loop until q is not empty.
  • Initialize temp_node = q.front() and print temp_node->data.
  • Push temp_node’s children i.e. temp_node -> left then temp_node -> right to q
  • Pop front node from q.

#include <bits/stdc++.h>
using namespace std;

// A Binary Tree Node
struct Node {
    int data;
    struct Node *left, *right;
};

// Iterative method to find height of Binary Tree
void printLevelOrder(Node* root)
{
    // Base Case
    if (root == NULL)
        return;

    // Create an empty queue for level order traversal
    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);
    }
}

// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

// Driver program to test above functions
int main()
{
    // Let us create binary tree shown in above diagram
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    cout << "Level Order traversal of binary tree is \n";
    printLevelOrder(root);
    return 0;
}

write your code here: Coding Playground

Time Complexity: O(N) where n is the number of nodes in the binary tree.

Auxiliary Space: O(N) where n is the number of nodes in the binary tree.

Hope this article gave you a clear understanding of the concept. To check out similar topics, do visit the Discussion Forum and Board Infinity Blogs.