Binary Tree Level Order Traversal

Given a Binary Tree, print level order traversal.

Example, Input Binary Tree

Output

10
5 20
4 8 15 25

Algorithm

We will discuss two ways to print the level order traversal of the binary tree. Both use queue and are very similar.

Level Order Traversal Using Queue

First Approach

As we know, queue follows First In First Out principle. If we traverse the Binary Tree using the queue, we are traversing it in level order. For example,

1. Initialize a queue.
2. Push root to queue.
3. Pop queue and store popped element in temp.
4. Print data stored in temp.
5. Push temp.left in the queue if it’s not null.
6. Push temp.right in the queue if it’s not null.
7. Repeat steps 3 to 6 until the queue is empty.

If we apply the above algorithm on the input binary tree, we get

10 5 20 4 8 15 25

The problem with the above algorithm is it doesn’t separate nodes at different levels with a newline.

To separate the nodes by a newline, we use a null node. If we encounter a null node then that means we have visited all nodes on the current level and we can print a newline. After printing the newline, we again insert a null node to the queue. Since we are inserting a null node at the end of each level, this makes sure that all the nodes that were inserted before null are at the same level.

Steps

1. Initialize queue which stores data of type node.
2. Push root node to queue.
3. Push null to queue.
4. Pop the queue and store the popped node in temp.
5. If temp is null
   • Print newline.
   • If the queue is not empty, push null again to the queue.
6. If temp is not null
   • Print the value of node temp.
   • Push temp.left to queue if it is not null.
   • Push temp.right to queue if it is not null.
7. Keep Repeating steps 4 to 5 until the queue is empty.

Code

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

// tree node structure
struct node {
	int d; // data
	node* left, * right;

	node(int data) {
		d = data;
		left = right = NULL;
	}

};

void PrintLevelOrder(node* root) {
	queue<node*> q;
	q.push(root);
	q.push(NULL);
	while (!q.empty()) {
		node* t = q.front();
		q.pop();

		// t==NULL means 
		// we have visited all nodes
		// of a level
		// we print a newline to seperate
		// nodes of different levels
		if (t == NULL) {
			cout << endl;
			if (!q.empty())
				q.push(NULL);
		}
		else {
			cout << t->d << ' ';
			if (t->left != NULL)
				q.push(t->left);
			if (t->right != NULL)
				q.push(t->right);
		}

	}
}

// insert data into the binary tree
node* InsertInBST(node* root, int data) {
	if (root == NULL) {
		return (new node(data));
	}
	if (root->d >= data) {
		root->left = InsertInBST(root->left, data);
	}
	else
		root->right = InsertInBST(root->right, data);
	return root;
}


int main()
{
	// root node of binary tree
	node* root = NULL;
	root = InsertInBST(root, 10);
	root = InsertInBST(root, 5);
	root = InsertInBST(root, 20);
	root = InsertInBST(root, 4);
	root = InsertInBST(root, 8);
	root = InsertInBST(root, 15);
	root = InsertInBST(root, 25);

	cout << "LEVEL ORDER TRAVERSAL OF BINARY TREE: " << endl;
	PrintLevelOrder(root);

}

Output

LEVEL ORDER TRAVERSAL OF BINARY TREE:
10
5 20
4 8 15 25

Second Approach

This very similar to the first approach. The only difference is instead of printing 1 node on each iteration, we will print nodes at same level in one iteration.

Steps

1. Initialize queue which stores data of type node.
2. Push root node to queue.
3. Push null to queue.
4. Pop the queue and store the popped element in temp.
   • Print data in temp.
   • Push temp.left to the queue if it’s not null.
   • Push temp.right to queue if it’s not null.
5. Repeat step 4 until temp is null.
6. Print newline.
7. Repeat steps 3 to 6 until the queue is empty.

Code

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

// binary tree node
struct node {
	int d; // data
	node* left, * right;

	node(int data) {
		d = data;
		left = right = NULL;
	}

};

void PrintLevelOrder(node* root) {
	queue<node*> q;
	q.push(root);

	while (!q.empty()) {
		// inserting NULL
		// it seperates the nodes of current level and the next level
		q.push(NULL);

		node* temp;

		// this loop prints all the nodes before NULL in the queue
		// all the nodes before NULL are in same level
		// all the nodes pushed in the queue in the loop
		// have 1 level grater than the current level
		// they are printed in the next iteration
		while (q.front() != NULL) {
			temp = q.front();
			cout << temp->d << ' ';
			if (temp->left != NULL)	q.push(temp->left);
			if (temp->right != NULL)	q.push(temp->right);
			q.pop();
		}

		// removing the extra NULL from the queue
		q.pop();

		// printing newline since we have visited
		// all nodes at current level
		cout << endl;
	}
}

// inserting data in binary tree
node* InsertInBST(node* root, int data) {
	if (root == NULL) {
		return (new node(data));
	}
	if (root->d >= data) {
		root->left = InsertInBST(root->left, data);
	}
	else
		root->right = InsertInBST(root->right, data);
	return root;
}


int main()
{
	// root node of binary tree
	node* root = NULL;
	root = InsertInBST(root, 10);
	root = InsertInBST(root, 5);
	root = InsertInBST(root, 20);
	root = InsertInBST(root, 4);
	root = InsertInBST(root, 8);
	root = InsertInBST(root, 15);
	root = InsertInBST(root, 25);

	cout << "LEVEL ORDER TRAVERSAL OF BINARY TREE: " << endl;
	PrintLevelOrder(root);

}

Output

LEVEL ORDER TRAVERSAL OF BINARY TREE:
10
5 20
4 8 15 25

Time Complexity: O(N)
Space Complexity: O(N)
N: Number of Nodes in the Binary Tree

References

https://en.wikipedia.org/wiki/Binary_tree
https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_of_binary_tree