Print level order traversal of Binary Tree using Queues

Level order traversal of a tree is breadth-first traversal for the tree. Print all the nodes of the Binary tree in level order traversal style.

Binary search tree

METHOD 1 (Use function to print a given level)

Algorithm:
There are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from the root.

Level Order Traversal tree

Output:

Level order traversal of binary tree is - 
1 2 3 4 5

Time Complexity: O(n²) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n²).

For line by line, A simple solution is to print use the recursive function and print a new line after every call to PrintGivenLevel().

Okay, How to Modify O(N²)?

METHOD 2 (Use One Queue)

Algorithm:
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

Implementation:
Here is a simple implementation of the above algorithm. Queue is implemented using an array with maximum size of 500. We can implement queue as linked list also.

First insert the root and a null element into the queue. This null element acts as a delimiter. Next pop from the top of the queue and add its left and right nodes to the end of the queue and then print the top of the queue. Continue this process till the queues become empty.

LevelOrder using One Queue in O(n).

Time Complexity: O(n) in the worst case. traversing each element throughout the Queue is done in O(n).

METHOD 3: Using Two Queues

We can insert the first level in first queue and print it and while popping from the first queue insert its left and right nodes into the second queue. Now start printing the second queue and before popping insert its left and right child nodes into the first queue. Continue this process until both the queues become empty.

Output :

1
2 3
4 5 6

Time Complexity: O(n) operations on both the queues are done one after another in N operations. hence O(n).

References:

https://en.wikipedia.org/wiki/Breadth-first_search

https://leetcode.com/playground/K9R66piQ

https://leetcode.com/playground/ycR7S8QB

find more and more knowledgeable resources related to #ai #machinelearning #deeplearning #python…https://twitter.com/Ajinkya_Tweets

Ajinkya Jawale, https://www.linkedin.com/in/ajinkya-jawale-b3421a12a/

https://angel.co/ajinkya-jawalereach me here, ajinkyajawale14499@gmail.com

gracies!