Level Order Traversal | Board Infinity

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.