Level Order (Breadth First Search) Traversal of Binary Tree
Level Order (Breadth First Search) Traversal of Binary Tree
Introduction to level order traversal
In the DFS traversal of a binary tree, we access nodes in three different orders: preorder, postorder, and inorder. Now there is another traversal that can access nodes in level-by-level order. This is called level order traversal or breadth-first search traversal. In the short form, we also call it BFS traversal.
A binary tree is organized into different levels where the root node is at the topmost level (0th level). So the idea of level order traversal is: We start by processing the root node, then process all nodes at the first level, second level, and so on. In other words, we explore all nodes at the current level before moving on to nodes at the next level.
Recursive approach of BFS or level order traversal
This is a brute force idea, where we move from the top to the bottommost level using a loop and process nodes at each level using recursion. The idea looks simple, but implementation would be a little tricky.
The objective to discuss this approach is related to problem-solving. In the recursive solution of a few tree problems, sometimes we pass extra parameters or use helper functions to generate the correct output.
Let’s think about the implementation of recursive BFS traversal:
- The number of levels is equal to the height of the tree. So we first calculate the height of the tree (h) using the function height(root).
- Now we run a loop from l = 0 to h - 1 and access each level in the tree. Inside the loop, we use the function processCurrentLevel(root, l) to visit and process nodes at the current level l.
How do we implement the function processCurrentLevel(root, l)? Let's think! In a standard level-order traversal, we traverse the nodes from left to right at any given level. So we can split the problem into two parts:
1) Traversing all nodes at distance l in the left subtree: We first recursively process all nodes at level l in the left subtree. For this, we call the same function with root->left and l - 1 as function parameters. Why? Because if the current level is l distance from the root, then it would be l - 1 distance away from root->left.
2) Traversing all the nodes at distance l in the right subtree: Now we recursively process all nodes at level l in the right subtree. For this, we call the same function with root->right and l - 1 as function parameters. Why? Because if the current level is l distance from the root, then it would be l - 1 distance away from root->right.
At each step of the recursive call, we are moving one level down. When l == 0, we will be at a node that is distance l from the root. So we process this node. In this way, we can access all nodes at level l recursively.
Implementation code C++
int
height
(
TreeNode*
root)
{
if
(
root ==
NULL
)
return
0
;
else
{
int
leftHeight =
height
(
root->
left)
;
int
rightHeight =
height
(
root->
right)
;
if
(
leftHeight >
rightHeight)
return
(
leftHeight +
1
)
;
else
return
(
rightHeight +
1
)
;
}
}
void
processCurrentLevel
(
TreeNode*
root,
int
l)
{
if
(
root ==
NULL
)
return
;
if
(
l ==
0
)
cout<<
root->
data;
else
if
(
l >
0
)
{
processCurrentLevel
(
root->
left,
l -
1
)
;
processCurrentLevel
(
root->
right,
l -
1
)
;
}
}
void
recursiveLevelOrder
(
TreeNode*
root)
{
int
h =
height
(
root)
;
for
(
int
l =
0
;
l <
h;
l =
l +
1
)
processCurrentLevel
(
root,
l)
;
}
Implementation code Python
def
height
(
root)
:
if
root is
None
:
return
0
else
:
left_height =
height(
root.
left)
right_height =
height(
root.
right)
if
left_height >
right_height:
return
left_height +
1
else
:
return
right_height +
1
def
process_current_level
(
root,
l)
:
if
root is
None
:
return
if
l ==
0
:
print
(
root.
data)
elif
l >
0
:
process_current_level(
root.
left,
l -
1
)
process_current_level(
root.
right,
l -
1
)
def
recursive_level_order
(
root)
:
h =
height(
root)
for
l in
range
(
h)
:
process_current_level(
root,
l)
Implementation code Java
public
class
LevelOrderTraversal
{
private
int
height
(
TreeNode
root)
{
if
(
root ==
null
)
return
0
;
else
{
int
leftHeight =
height
(
root.
left)
;
int
rightHeight =
height
(
root.
right)
;
if
(
leftHeight >
rightHeight)
return
(
leftHeight +
1
)
;
else
return
(
rightHeight +
1
)
;
}
}
private
void
processCurrentLevel
(
TreeNode
root,
int
l)
{
if
(
root ==
null
)
return
;
if
(
l ==
0
)
System
.
out.
print
(
root.
data +
" "
)
;
else
if
(
l >
0
)
{
processCurrentLevel
(
root.
left,
l -
1
)
;
processCurrentLevel
(
root.
right,
l -
1
)
;
}
}
public
void
recursiveLevelOrder
(
TreeNode
root)
{
int
h =
height
(
root)
;
for
(
int
l =
0
;
l <
h;
l =
l +
1
)
processCurrentLevel
(
root,
l)
;
}
}
Time and space complexity analysis
To process nodes at a specific level l, we recursively call the function processCurrentLevel() for both the left and right subtree. In other words, for each level l, we traverse l - 1 level down and recursively access each node from level 0 to level l. So one idea becomes clear: the total number of operations depends on the height of the tree.
The worst-case scenario would be a skewed tree where each node has only one child, resulting in a tree height of O(n). In this case, processCurrentLevel() takes O(n) time for the last level, O(n-1) time for the second-last level, and so on. So time complexity = O(n) + O(n - 1) + .. + O(1) = O(n + n-1 + ... + 1) = O(n^2). What about the best-case scenario? Think and explore!
The space complexity depends on the size of the recursion call stack, which is equal to the height of the tree. So skewed tree will be the scenario of the worst case and recursion will use O(n) space for the call stack. The space complexity in the worst case = O(n).
Efficient approach: BFS or level order traversal using queue
Now critical questions are: Can we optimize the time complexity of BFS traversal? Can we traverse the tree level by level in O(n) time complexity? Let's think! If we observe the order of nodes in level order traversal:
- We first process the root node at level 0, and then we process the left and right child at level 1 (assuming left to right order).
- Similarly, at the second level, we first process children of the left child of the root then process children of the right child. This process goes on for all levels.
So one idea is clear: If we first process a node x at any given level, then the children of node x will be processed before the children of any other node at the next level. In other words, if node x comes before node y at the same level, then at the next level, we will process the children of node x before processing the children of node y. This is the First In First Out (FIFO) order of processing nodes. So we can use a queue data structure to simulate the level order or breadth-first search (BFS) traversal.
Implementation steps: BFS traversal using queue
Step 1: We create an empty queue treeQueue and initialize it with the root node.
Step 2: Now we run a loop until the treeQueue is empty. Inside the loop, we declare a variable called currNode to keep track of the current node during the traversal.
- We start the loop by removing the front node from the treeQueue and assigning it to currNode.
- Now we process currNode and insert its left and right child nodes into the treeQueue if they exist: 1) If the left child of currNode is not NULL, we insert it into the treeQueue 2) If the right child of currNode is not NULL, we insert it into the treeQueue.
Step 3: After processing the rightmost node at the last level, there are no more nodes inside the queue to process. We exit the loop, and the level order traversal is complete.
Implementation code C++
void
iterativeLevelOrder
(
TreeNode*
root)
{
if
(
root ==
NULL
)
return
;
queue<
TreeNode*
>
treeQueue;
treeQueue.
push
(
root)
;
while
(
treeQueue.
empty
(
)
==
false
)
{
TreeNode*
currNode =
treeQueue.
front
(
)
;
treeQueue.
pop
(
)
;
cout <<
currNode->
data <<
" "
;
if
(
currNode->
left !=
NULL
)
treeQueue.
push
(
currNode->
left)
;
if
(
currNode->
right !=
NULL
)
treeQueue.
push
(
currNode->
right)
;
}
}
Implementation code Python
def
iterativeLevelOrder
(
root)
:
if
root is
None
:
return
treeQueue =
[
]
treeQueue.
append(
root)
while
len
(
treeQueue)
>
0
:
currNode =
treeQueue.
pop(
0
)
print
(
currNode.
data,
end=
" "
)
if
currNode.
left is
not
None
:
treeQueue.
append(
currNode.
left)
if
currNode.
right is
not
None
:
treeQueue.
append(
currNode.
right)
Implementation code Java
class
BFSTreeTraversal
{
public
void
iterativeLevelOrder
(
TreeNode
root)
{
if
(
root ==
null
)
return
;
Queue
<
TreeNode
>
treeQueue =
new
LinkedList
<
>
(
)
;
treeQueue.
add
(
root)
;
while
(
treeQueue.
isEmpty
(
)
==
false
)
{
TreeNode
currNode =
treeQueue.
poll
(
)
;
System
.
out.
print
(
currNode.
data +
" "
)
;
if
(
currNode.
left !=
null
)
treeQueue.
add
(
currNode.
left)
;
if
(
currNode.
right !=
null
)
treeQueue.
add
(
currNode.
right)
;
}
}
}
Time complexity analysis of the BFS traversal
Suppose n number of nodes are given in the input.
- The time complexity of each enqueue and dequeue operation = O(1).
- We are doing two queue operations for each node inside the loop: Inserting once into the queue and deleting once from the queue. So total queue operations = 2n.
- Overall time complexity = Total queue operations * Time complexity of each queue operation = 2n * O(1) = O(n)
Space complexity analysis of the BFS traversal
Space complexity is equal to the queue size. We process nodes level by level, so the max queue size depends on the level with the maximum number of nodes or max-width of the binary tree. If the maximum width of the binary tree is w, then space complexity = O(w). The idea is simple: w depends on the structure of a given binary tree. How? Let’s think!
Worst case: When tree is balanced
When tree is balanced, the last level will have maximum width or maximum number of nodes, which will be 2^h (where h is the height of the tree). For balanced tree, h = logn and required size of the queue = O(2^h) = O(2^(log n)) = O(n). Space complexity = O(n).
Best case: When tree is skewed
In such case, every level will have maximum of one node. So at any point, there will be at most one node in the queue. So required size of the queue = O(1). Space complexity = O(1).
BFS vs DFS traversal of binary tree
- Both traversals require O(n) time as they visit every node exactly once.
- Depth-first traversal starts from the root, goes to the depth as far as possible, and then backtracks from there. In other words, it visits nodes from bottom of the tree. But in breadth-first search, we explore nodes level by level i.e. in order of their distance from the root node. So if our problem is to search for something closer to the root, we would prefer BFS. And if we need to search for something in the depth of tree or node closer to leaf, we would prefer DFS.
- In BFS traversal, we use queue data structure to store nodes of different levels. But in DFS traversal, we use the stack (If recursive, system use call stack) to store all ancestors of a node.
- The memory taken by both BFS and DFS depends on the structure of tree. Extra space required for BFS Traversal is O(w), but additional space needed for DFS Traversal is O(h). Here w = maximum width of binary tree and h = maximum height of binary tree. In the worst case, both require O(n) extra space, but worst cases occur for different types of trees. For example, space needed for BFS Traversal is likely to be more when a tree is more balanced, and extra space for DFS Traversal is likely to be more when a tree is less balanced.
- Sometimes, when node order is not required in problem-solving, we can use both BFS and DFS traversals. But in some cases, such things are not possible. We need to identify the use case of traversal to solve the problems efficiently.
Problems to practice using BFS traversal
- Level order traversal in spiral form
- Reverse Level Order Traversal
- Left View of Binary Tree
- Maximum width of a binary tree
- Min Depth of Binary Tree
- Level with the maximum number of nodes
- Count the number of nodes at a given level
- Convert a binary tree into a mirror tree
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!
While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.
Breadth-First Search and Depth-First Search are two techniques of traversing graphs and trees. In this tutorial, we will focus mainly on BFS and DFS traversals in trees.
The algorithm begins at the root node and then it explores each branch before backtracking. It is implemented using stacks. Often while writing the code, we use recursion stacks to backtrack. By using recursion we are able to take advantage of the fact that left and right subtrees are also trees and share the same properties.
For Binary trees, there are three types of DFS traversals.
- In-Order
- Pre-Order
- Post-Order
This algorithm also begins at the root node and then visits all nodes level by level. That means after the root, it traverses all the direct children of the root. After all direct children of the root are traversed, it moves to their children and so on. To implement BFS we use a queue.
For Binary trees, we have Level Order Traversal which follows BFS.
Let the tree under consideration be:
The structure of TreeNode class is as follows :
static
class
TreeNode
{
int
data;
TreeNode
left,
right;
public
TreeNode
(
int
key)
{
data =
key;
left =
right =
null
;
}
}
In pre-order traversal of a binary tree, we first traverse the root, then the left subtree and then finally the right subtree. We do this recursively to benefit from the fact that left and right subtrees are also trees.
The algorithm for pre-order traversal is as follows:
- Traverse the root.
- Call preorder() on the left subtree.
- Call preorder() on the right subtree.
The Pre-Order traversal of the tree above is:
0 1 3 4 2
The java code is as follows:
static
void
preorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
System
.
out.
print
(
TreeNode
.
item +
"->"
)
;
preorder
(
TreeNode
.
left)
;
preorder
(
TreeNode
.
right)
;
}
In-order traversal of a binary tree first traverses the left subtree then the root and finally the right subtree.
The algorithm for in-order traversal is as follows:
- Call inorder() on left subtree.
- Traverse the root.
- Call inorder() on right subtree.
The in-order traversal of the tree above is:
3 1 4 0 2
The java code is as follows :
static
void
inorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
inorder
(
TreeNode
.
left)
;
System
.
out.
print
(
TreeNode
.
item +
"->"
)
;
inorder
(
TreeNode
.
right)
;
}
Post-order traversal of a binary tree first traverses the left subtree then the right subtree and then finally the root.
The algorithm for post-order traversal is as follows:
- Call postorder() on left subtree.
- Call postorder() on right subtree.
- Traverse the root.
The post-order traversal of the tree above is:
3 4 1 2 0
The java code is as follows :
static
void
postorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
postorder
(
TreeNode
.
left)
;
postorder
(
TreeNode
.
right)
;
System
.
out.
print
(
TreeNode
.
item +
"->"
)
;
}
Level order traversal uses a queue to keep track of nodes to visit. After visiting a node, its children are put in the queue. To get a new node to traverse, we take out elements from the queue.
The algorithm is as follows:
- Initialize an empty queue
- Start with setting temp as root
- Run a Loop till queue is not empty
- Print data from temp.
- Enqueue temp’s children in the order left then right.
- Dequeue a node from the queue and assign it’s value to temp.
Level order traversal of the tree above is :
0 1 2 3 4
The java code is as follows :
static
void
printLevelOrder
(
TreeNode
root)
{
Queue
<
TreeNode
>
queue =
new
LinkedList
<
TreeNode
>
(
)
;
queue.
add
(
root)
;
while
(
!
queue.
isEmpty
(
)
)
{
TreeNode
temp =
queue.
poll
(
)
;
System
.
out.
print
(
temp.
data +
" "
)
;
if
(
temp.
left !=
null
)
{
queue.
add
(
temp.
left)
;
}
if
(
temp.
right !=
null
)
{
queue.
add
(
temp.
right)
;
}
}
}
The complete Java code is given below :
package
com
.
JournalDev
;
import
java
.
util.
LinkedList
;
import
java
.
util.
Queue
;
public
class
Main
{
static
class
TreeNode
{
int
data;
TreeNode
left,
right;
public
TreeNode
(
int
key)
{
data =
key;
left =
right =
null
;
}
}
static
void
preorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
System
.
out.
print
(
TreeNode
.
data +
" "
)
;
preorder
(
TreeNode
.
left)
;
preorder
(
TreeNode
.
right)
;
}
static
void
inorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
inorder
(
TreeNode
.
left)
;
System
.
out.
print
(
TreeNode
.
data +
" "
)
;
inorder
(
TreeNode
.
right)
;
}
static
void
postorder
(
TreeNode
TreeNode
)
{
if
(
TreeNode
==
null
)
return
;
postorder
(
TreeNode
.
left)
;
postorder
(
TreeNode
.
right)
;
System
.
out.
print
(
TreeNode
.
data +
" "
)
;
}
static
void
printLevelOrder
(
TreeNode
root)
{
Queue
<
TreeNode
>
queue =
new
LinkedList
<
TreeNode
>
(
)
;
queue.
add
(
root)
;
while
(
!
queue.
isEmpty
(
)
)
{
TreeNode
tempNode =
queue.
poll
(
)
;
System
.
out.
print
(
tempNode.
data +
" "
)
;
if
(
tempNode.
left !=
null
)
{
queue.
add
(
tempNode.
left)
;
}
if
(
tempNode.
right !=
null
)
{
queue.
add
(
tempNode.
right)
;
}
}
}
public
static
void
main
(
String
args[
]
)
{
TreeNode
root =
new
TreeNode
(
0
)
;
root.
left =
new
TreeNode
(
1
)
;
root.
right =
new
TreeNode
(
2
)
;
root.
left.
left =
new
TreeNode
(
3
)
;
root.
left.
right =
new
TreeNode
(
4
)
;
System
.
out.
println
(
"Inorder traversal"
)
;
inorder
(
root)
;
System
.
out.
println
(
"\nPreorder traversal "
)
;
preorder
(
root)
;
System
.
out.
println
(
"\nPostorder traversal"
)
;
postorder
(
root)
;
System
.
out.
println
(
"\nLevelorder traversal"
)
;
printLevelOrder
(
root)
;
}
}
Output :
Inorder traversal
3 1 4 0 2
Preorder traversal
0 1 3 4 2
Postorder traversal
3 4 1 2 0
Levelorder traversal
0 1 2 3 4
This tutorial was about BFS and DFS traversals in binary trees. To get DFS implementation in C++ refer to this tutorial. For C++ implementation of level order traversal refer to this tutorial.
Level Order (Breadth First Search) Traversal of Binary Tree
Breadth-First Search (BFS) and Depth-First Search (DFS ...
- 0