In the DFS traversal of a binary tree, we access nodes in three different orders — preorder, postorder and inorder. Now we have another traversal that accesses 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 the root node is at the topmost level (0th level). So we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.
This is a brute force idea where we go through each level using a loop and process nodes at each level using recursion. The idea is simple, but implementation is a little tricky. The objective to discuss this approach is related to problem-solving. In the recursive solution of few tree problems, sometimes we pass extra parameters or use a helper function to generate the correct output. Let’s think about the implementation of the recursive BFS traversal:
How we implement the function processCurrentLevel(root, l)? Let’s think! We can split the problem into two parts:
Processing nodes at the level l
Calculating the height of the tree
Time and space complexity analysis
For each function 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: the total number of operations depends on the height of the tree. Think!
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 the number of nodes in the skewed 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() uses O(n) space for the call stack. For a balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree).
Now the critical question is — can we optimize the time complexity of the 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. We first process the root node at level 0, and then we process the left and right child at level 1 (assuming the order from left to right). Similarly, at the second level, we first process the children of the left child of the root then process the children of the right child. This process goes on for all the levels in the tree. So one idea is clear: at any level, the node which will be processed first at any given level, the children of that node will be processed first at the next level. So this is the First In First Out order of processing nodes, and we can think to use the queue data structure to simulate the BFS traversal.
Implementation steps: BFS traversal using queue
We start the loop by deleting the front node from the treeQueue and assign it with currNode. We process the currNode and insert the left and right child into the treeQueue.
TreeNode currNode = treeQueue.dequeue() process (currNode->data)
If the left child of currNode is not NULL, we insert the left child into the treeQueue.
if (currNode->left != NULL) treeQueue.enqueue(currNode->left)
If the right child of currNode is not NULL, we insert the right child into the treeQueue.
if (currNode->right != NULL) treeQueue.enqueue(currNode->right)
Pseudocode of BFS traversal using queue
Time complexity analysis of the BFS traversal
The space complexity analysis of the BFS traversal
Space complexity is equal to the queue size. We process nodes level by level, so max queue size depends on the level with a 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: the width of w depends on the structure of the given binary tree. How? Let’s think!
Worst case: When the tree is balanced
When the tree is balanced, the last level will have the maximum width or the maximum number of nodes, which will be 2^h (where h is the height of the tree). For a balanced tree, h = logn and required size of the queue = O(2^h) = O(2 ^ (log n)) = O(n). So space complexity = O(n)
Best case: When the tree is a skewed tree or a linked list
In such a case, every level will have a maximum of one node, and thus at any point of time, there will be at most one node in the queue. So required size of the queue = O(1). So space complexity = O(1)
Enjoy learning, Enjoy coding, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.