Problem Statement:
Given a binary tree. You are required to populate the values of all nodes of each level from left to right in separate sub-arrays.
Example 1:
Example 2:
Level Order Traversal or Breadth-First Search
Breadth-First Search (BFS) also known as Level Order Traversal is one of the techniques to traverse the tree. This technique traverses the tree in a level-by-level fashion.
We will use a Queue data structure to achieve this. Here are the steps of our algorithm.
Step 1:
We will start by pushing the root node into the queue.
Step 2:
Now, we will calculate the queueSize which will tell us the size of the current level. In this case, the queueSize is 1 and hence we have only one element in the first level.
Let’s call queueSize as levelSize. Therefore, we will run a loop for levelSize times, and in each iteration, we will pop the element out from the queue and insert it into the separate list.
Hence, the loop will run only one time, and node 4 will be popped out and inserted in a separate list. While popping out node 4, we will insert the left and right nodes of node 4 into the queue for the next level.
Step 3:
Now, we will again calculate the queueSize which will tell us the size of the current level. In this case, the queueSize is 2 and hence we have two elements in the second level.
Therefore, we will run a loop for (queueSize) or levelSize times, and in each iteration, we will pop the element out from the queue and insert it into the separate list.
This time, the loop will run two times.
- Node 6 will be popped out and inserted in a separate list. While popping out node 6, we will insert the left and right nodes of node 6 into the queue for the next level. But in this case, we don’t have right node of node 6. Hence, only left node will be inserted.
- Node 8 will be popped out and inserted in the same list. While popping out node 8, we will insert the left and right nodes of node 8 into the queue for the next level.
- Now, the loop will end and hence we will have another level stored in a different list.
Step 4:
Now, we will again calculate the queueSize which will tell us the size of the current level. In this case, the queueSize is 3 and hence we have three elements in the third level.
Therefore, we will run a loop for (queueSize) or levelSize times, and in each iteration, we will pop the element out from the queue and insert it into the separate list.
This time, the loop will run three times.
- Node 9 will be popped out and inserted in a separate list. While popping out node 9, we will insert the left and right nodes of node 9 into the queue for the next level. But in this case, we don’t have left and right nodes for node 9. Hence, no node will be inserted.
- Node 5 will be popped out and inserted in the same list. While popping out node 5, we will insert the left and right nodes of node 5 into the queue for the next level. But in this case also, we don’t have left and right nodes for node 5. Hence, no node will be inserted.
- Similarly, Node 7 will be popped out and inserted in the same list. While popping out node 7, we will insert the left and right nodes of node 7 into the queue for the next level. But in this case also, we don’t have left and right nodes for node 7. Hence, no node will be inserted.
- Now, the loop will end and hence we will have another level stored in a different list.
Step 5:
Now, the queue becomes empty and hence the loop will break. And we will have our answer stored in a list having different levels stored in separate lists.
Let’s look at the code.
Java Code:
import java.util.*;
class Node {
int data;
Node left, right;
public Node(int key) {
data = key;
left = right = null;
}
}
class LevelOrderTraversal {
static Node root;
LevelOrderTraversal() {
root = null;
}
public static List<List<Integer>> traverse(Node root) {
List<List<Integer>> bfs = new ArrayList<>();
if(root == null) return bfs;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for(int i = 0; i < levelSize; i++) {
Node current = queue.poll();
currentLevel.add(current.data);
if(current.left != null)
queue.offer(current.left);
if(current.right != null)
queue.offer(current.right);
}
bfs.add(currentLevel);
}
return bfs;
}
public static void main (String[] args) {
root = new Node(4);
root.left = new Node(6);
root.right = new Node(8);
root.left.left = new Node(9);
root.right.left = new Node(5);
root.right.right = new Node(7);
List<List<Integer>> ans = traverse(root);
for(List<Integer> level : ans) {
for(int node : level) {
System.out.print(node + " ");
}
System.out.println();
}
}
}
Output:
4 6 8 9 5 7
CPP Code:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
Node(int data) {
this->data = data;
left = right = NULL;
}
};
struct Node *root = NULL;
vector<vector<int>> traverse(struct Node *root) {
vector<vector<int>> bfs;
if(root == NULL)
return bfs;
queue<Node *> queue;
queue.push(root);
while(!queue.empty()) {
int levelSize = queue.size();
vector<int> currentLevel;
for(int i = 0; i < levelSize; i++) {
Node *current = queue.front();
queue.pop();
currentLevel.push_back(current->data);
if(current->left != NULL)
queue.push(current->left);
if(current->right != NULL)
queue.push(current->right);
}
bfs.push_back(currentLevel);
}
return bfs;
}
int main(int argc, char const *argv[]) {
root = new Node(4);
root->left = new Node(6);
root->right = new Node(8);
root->left->left = new Node(9);
root->right->left = new Node(5);
root->right->right = new Node(7);
vector<vector<int>> ans = traverse(root);
for(auto level : ans) {
for(auto node : level) {
cout << node << " ";
}
cout << endl;
}
}
Output:
4 6 8 9 5 7
Python Code:
from collections import *
class Node:
def __init__(self, data):
self.data = data
self.right = self.left = None
class LevelOrderTraversal:
def __init__(self):
self.root = None
def traverse(self, root):
bfs = []
if root is None:
return bfs
queue = deque([])
queue.append(self.root)
while len(queue) != 0:
level_size = len(queue)
current_level = []
for i in range(level_size):
current = queue.popleft()
current_level.append(current.data)
if current.left is not None:
queue.append(current.left)
if current.right is not None:
queue.append(current.right)
bfs.append(current_level)
return bfs
if __name__ == '__main__':
tree = LevelOrderTraversal()
tree.root = Node(4)
tree.root.left = Node(6)
tree.root.right = Node(8)
tree.root.left.left = Node(9)
tree.root.right.left = Node(5)
tree.root.right.right = Node(7)
ans = tree.traverse(tree.root)
for level in ans:
for node in level:
print(node, end = " ")
print()
Output:
4 6 8 9 5 7
Time and Space Complexity:
The time complexity of the above algorithm is O(N), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.
The space complexity of the above algorithm will be O(N) as we need to return a list containing the level order traversal. We will also need O(N) space for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need O(N) space to store them in the queue.