Level Order Traversal of Binary 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.

Problem Statement

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

Example 1:

Input:

Output:

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

Example 2:

Input:

Output:

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

There are two approaches to solving this problem:

1. 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 the 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 the root is null then return.
  • Check if the 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

1. Level Order Traversal in C

2. Level Order Traversal in C++

3. Level Order Traversal in Java

4. 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).

2. 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 of the above Approach

1. C++ Implementation

2. Java Implementation

3. 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

• Zigzag Level Order Traversal BT
• Right View Of Binary Tree
• Cousins In Binary Tree
• Identical Binary Trees
• 2-Sum Binary Tree
• Min Depth of Binary Tree
• Last Node in a Complete Binary Tree
• Max Sum Path in Binary Tree

Frequently Asked Questions

Q.1: What is the level order traversal of a tree?

Ans: 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.

Q.2: How do you do level order traversal?

Ans: Level order traversal can be done by using a queue and traversing nodes by depth.

Q.3: Is Level order traversal the same as BFS?

Ans: Yes, both the algorithms are the same as both traverse the nodes by depth.

Q.4: When should I use level order traversal?

Ans: 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.

Additional Resources

• Binary Tree
• Top view of Binary Tree
• Diameter of a Binary Tree
• Bottom View of Binary Tree
• Inorder Traversal of a Binary Tree
• Left View of a Binary Tree