Level Order Traversal of Binary Tree

Problem Statement

Given a binary tree, the task is to print the level order traversal line by line of the tree

Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc.

Examples:
Input:

Output:
Level1 nodes: 1
Level 2 nodes: 2,3
Level 3 nodes: 4,5
Level 4 nodes 6,7

Input:

Output:
Level1 nodes: 50
Level 2 nodes: 35,57
Level 3 nodes: 30,40,52,58
Level 4 nodes: 11

Recursive Approach

There are basically two functions in this approach. One of them is used to print all nodes at a particular level (CurrentLevel), and another is used to print level order traversal of the tree (Levelorder).

• In the CurrentLevel function, we find the height of the tree and call the LevelOrder function for every level between 1 to height.
• In the LevelOrder function we pass two parameters level and root. we follow the below steps:
• First check if root is null then return.
• Check if level is equal to 1 then print the current root value.
• Now, call recursively call both the children of the current root with decrementing the value of level by 1.

Implementation of Recursive Approach

Level Order Traversal in Python

Time complexity: For a skewed tree, time complexity will be O(n^2).
Space complexity: For a skewed tree space complexity will be O(n) and for a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).

Level Order Traversal Using Queue

Firstly we insert the root into the queue and iterate over the queue until the queue is empty.
In every iteration, we will pop from the top of the queue and print the value at the top of the queue.
Then, add its left and right nodes to the end of the queue.

Implementation

Python Implementation

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

Practice Questions

What is the level order traversal of a tree?
Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc.

How do you do level order traversal?
Level order traversal can be done by using a queue and traversing nodes by depth.

Is Level order traversal the same as BFS?
Yes, both the algorithms are the same as both traverse the nodes by depth.

When should I use level order traversal?
Level order traversal is actually a Breadth-First Search, which can be used to solve many problems in graph theory, for example: Finding all nodes within one connected component.