Level Order Tree Traversal

version.cpp

/* C++ program to print level order traversal using STL */
#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 tarversal 
	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; 
} 

version.py

# Python program to print level order traversal using Queue 

# A node structure 
class Node: 
	# A utility function to create a new node 
	def __init__(self ,key): 
		self.data = key 
		self.left = None
		self.right = None

# Iterative Method to print the height of binary tree 
def printLevelOrder(root): 
	# Base Case 
	if root is None: 
		return
	
	# Create an empty queue for level order traversal 
	queue = [] 

	# Enqueue Root and initialize height 
	queue.append(root) 

	while(len(queue) > 0): 
		# Print front of queue and remove it from queue 
		print queue[0].data, 
		node = queue.pop(0) 

		#Enqueue left child 
		if node.left is not None: 
			queue.append(node.left) 

		# Enqueue right child 
		if node.right is not None: 
			queue.append(node.right) 

#Driver Program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 

print "Level Order Traversal of binary tree is -"
printLevelOrder(root) 

Time Complexity: O(n) where n is number of nodes in the binary tree
Space Complexity: O(n) where n is number of nodes in the binary tree
For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)

1. Create an empty queue q
2. temp_node = root /start from root/
3. Loop while temp_node is not NULL
   a) print temp_node->data.
   b) Enqueue temp_node’s children (first left then right children) to q
   c) Dequeue a node from q and assign it’s value to temp_node