In 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 in different levels where root node is at the topmost level (0th level). So the idea of level order traversal is: We start by processing 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.
This is a brute force idea, where we move from top to bottommost level using a loop and process nodes at each level using recursion. The idea looks simple, but implementation would be little tricky.
The objective to discuss this approach is related to problem-solving. In 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:
How we implement function processCurrentLevel(root, l)? Let’s think! We can split the problem into two parts:
class TreeNode
{
int data
TreeNode left
TreeNode right
}
void recursiveLevelOrder(TreeNode root)
{
int h = height(root)
for (int l = 0; l < h; l = l + 1)
processCurrentLevel(root, l)
}
Processing nodes at the level l
void processCurrentLevel(TreeNode root, int l)
{
if (root == NULL)
return
if (l == 0)
process(root->data)
else if (l > 0)
{
processCurrentLevel(root->left, l - 1)
processCurrentLevel(root->right, l - 1)
}
}
Calculating the height of tree
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)
}
}
For each recursive call processCurrentLevel(), we are going l - 1 level down in the left and right subtree. In other words, we are accessing each node from level 0 to level l and checking if l == 0 or not. So one idea is clear: Total number of operations depends on the height of the tree. Think!
The worst-case scenario would be the skewed tree where one node is present at each level. In this case, processCurrentLevel() takes O(n) time for the last level, O(n-1) time for the second last level, and so on. Here n is number of nodes in the tree. Time complexity = O(n) + O(n - 1) + .. + O(1) = O(n + (n-1) + ... + 1) = O(n^2). Critical question: What would be the best case analysis? Think!
Space complexity = O(n) in the worst case. For a skewed tree, processCurrentLevel() will use O(n) space for the call stack. For a balanced tree, the call stack uses O(log n) space. Note: The size of call stack is equal to the height of the tree.
Now critical questions are: Can we optimize the time complexity of BFS traversal? Can we traverse tree level by level in O(n) time complexity? Think!
Let's observe the order of nodes in level order traversal.
So one idea is clear: At any given level, node which will be processed first, children of that node will be processed first at the next level. This is First In First Out Order (FIFO Order) of processing nodes! So we can use queue data structure to simulate the BFS traversal. Think!
We start loop by removing front node from treeQueue and assigning it with currNode. We process the currNode and insert left and right child into treeQueue.
TreeNode currNode = treeQueue.dequeue()
process (currNode->data)
If left child of currNode is not NULL, we insert left child into treeQueue.
if (currNode->left != NULL)
treeQueue.enqueue(currNode->left)
If right child of currNode is not NULL, we insert right child into treeQueue.
if (currNode->right != NULL)
treeQueue.enqueue(currNode->right)
void iterativeLevelOrder(Treenode root)
{
if (root == NULL)
return
Queue<TreeNode> treeQueue
treeQueue.enqueue(root)
while (treeQueue.empty() == false)
{
TreeNode currNode = treeQueue.dequeue()
process(currNode->data)
if (currNode->left != NULL)
treeQueue.enqueue(currNode->left)
if (currNode->right != NULL)
treeQueue.enqueue(currNode->right)
}
}
Space complexity is equal to the queue size. We process nodes level by level, so max queue size depends on the level with maximum number of nodes or max-width of binary tree. If maximum width of binary tree is w, then space complexity = O(w). The idea is simple: w depends on the structure of 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, and thus 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)
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.