Level Order Traversal (BFS Traversal) of Binary Tree

Introduction

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.

If we observe, a binary tree is organized into different levels where root node is at the topmost level. So one idea is to traverse tree level by level i.e. we start from the root node (level 0), then process all nodes at the first level, second level, and so on. Here we explore all nodes at the current level before moving on to nodes at the next level.

The idea of level order traversal using queue

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 (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.

Let's observe another pattern: If we first process a node x at any given level, then the children of node x will be processed first at the next level. From another perspective: 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. So we can use a queue data structure to simulate the level order or BFS traversal.

Implementation steps

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 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 pseudocode

void levelOrderTraversal(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)
    }
}

Time complexity analysis

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: Inserting once into the queue and deleting once from the queue. So total queue operations = 2n.
• Time complexity = Total queue operations * Time complexity of one queue operation = 2n * O(1) = O(n)

Space complexity analysis

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, 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 one node. So at any point, there will be at most one node in the queue. So 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. 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 can prefer BFS. If we need to search for something in the depth of tree or node closer to leaf, we can prefer DFS.
• In BFS traversal, we use queue data structure to store nodes of different levels. 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 the given problem, we can use both BFS and DFS traversals. In some cases, such things are not possible. We need to identify the correct 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!