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.
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:
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.
//Calculate the height of the 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);
}
}
//Process nodes at the level l
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);
}
}
//Traverse nodes in level order traversal
void recursiveLevelOrder(TreeNode* root)
{
int h = height(root);
for (int l = 0; l < h; l = l + 1)
processCurrentLevel(root, l);
}
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)
public class LevelOrderTraversal
{
// Calculate the height of the tree
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);
}
}
// Process nodes at the level l
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);
}
}
// Traverse nodes in level order traversal
public void recursiveLevelOrder(TreeNode root)
{
int h = height(root);
for (int l = 0; l < h; l = l + 1)
processCurrentLevel(root, l);
}
}
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).
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:
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.
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.
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.
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);
}
}
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)
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);
}
}
}
Suppose n number of nodes are given in the input.
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).
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.