Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 39

Level-Order Traversal with a Queue

Recommended resources

In our last lesson, we delved into the "deep" traversal of binary trees using Depth-First Search (DFS), implementing preorder, inorder, and postorder traversals with recursion. You saw how the call stack implicitly managed the traversal path. Today, we pivot to a different strategy: exploring the tree in a "wide," level-by-level fashion.

This lesson focuses on implementing level-order traversal, which is a direct application of the Breadth-First Search (BFS) algorithm to trees. Instead of relying on recursion, you will use an explicit data structure—the Queue—to manage the order of node visits. This iterative approach is fundamental for solving a wide class of problems where you need to find the shortest path or explore nodes in order of their proximity to the root. This is a crucial algorithm for your DSA problem-solving toolkit and completes our foundational study of tree traversals.

1. From Depth to Breadth: The Logic of Level-Order Traversal

In the previous lesson, our DFS algorithms ventured as far down a branch as possible before backtracking. Level-order traversal does the opposite. It visits all nodes at a given level before moving on to the next.

For a tree like this:

  • Level 0: A
  • Level 1: B, C
  • Level 2: D, E, F, G

The level-order traversal would be: A, B, C, D, E, F, G.

To achieve this, we need a data structure that processes nodes in the order they are discovered. Recall from our earlier module on collections that a Queue operates on a First-In, First-Out (FIFO) principle. This makes it the perfect tool for the job. When we visit a node, we add its children to the back of the queue. The FIFO rule ensures that we will not visit those children until we have visited all other nodes that were already in the queue (i.e., all other nodes at the current level).

The algorithm is straightforward:

  1. Create an empty queue and add the root node to it.
  2. Loop as long as the queue is not empty.
  3. In each iteration:
    a. Remove the node from the front of the queue (dequeue).
    b. Process the dequeued node (e.g., print its value).
    c. Add its left child to the back of the queue (enqueue), if it exists.
    d. Add its right child to the back of the queue (enqueue), if it exists.

This animated GIF provides an excellent visual of this process in action. Notice how nodes are added to the right end of the queue and removed from the left, maintaining the level-by-level order.

This animation shows how a queue facilitates the level-order traversal of a binary tree. Nodes are added to the queue as they are discovered, and the FIFO mechanism ensures they are processed level by level.

The following static image breaks down the state of the queue after each level is processed, reinforcing the concept.

This diagram illustrates the contents of the queue at the beginning of each level's processing. The first step processes node 1, adding its children (2, 3) to the queue. The second step processes nodes 2 and 3, adding their children (4, 5, 6, 7), and so on.

2. Implementing Level-Order Traversal in Java

Now that you have the intuition, let's translate this logic into Java code. A popular variation of this problem, often seen in coding interviews, is not just to print the nodes but to return a List<List<Integer>>, where each inner list contains the nodes of one level. The following video provides an outstanding walkthrough of this exact problem.

L8. Level Order Traversal of Binary Tree | BFS | C++ | Java

This video from the "take U forward" channel clearly explains the level-order traversal algorithm and implements it in Java to produce a level-separated list.

Please watch the following segments: Introduction: The instructor first defines what level-order traversal output should look like. Algorithm Walkthrough: This is a crucial part. Pay close attention to how the queue is used and, importantly, how the size of the queue at the start of each level's processing is used to know how many nodes to process for that level. Java Code Explanation: The instructor walks through the Java code, connecting each line back to the algorithm discussed. Note the use of Queue<TreeNode> queue = new LinkedList<>();, which leverages the LinkedList class's implementation of the Queue interface.

To solidify your understanding, let's examine a complete, runnable code example from an article. This allows you to study the implementation at your own pace.

Breadth-First Search (BFS) and Depth-First Search (DFS ...

This DigitalOcean article provides a clean and complete implementation of all tree traversals, including a simple level-order method that prints to the console.

Please read the following sections: The printLevelOrder method: Find the section titled Level-Order Traversal. Analyze the printLevelOrder method provided. This is the most direct implementation of the algorithm we discussed. Full Code: Now, review the Complete Code Implementation. This shows how the TreeNode class, the traversal method, and the main method all fit together. You can copy, paste, and run this code yourself to see it in action, which is a great way to reinforce your learning.

3. Time and Space Complexity

Understanding the performance characteristics of an algorithm is just as important as knowing how to implement it. For level-order traversal:

  • Time Complexity: , where is the number of nodes in the tree. This is because every node is enqueued and dequeued exactly once.
  • Space Complexity: , where is the maximum width of the tree. The space is determined by the maximum number of nodes the queue holds at any given time. In the worst-case scenario (a complete or full binary tree), the last level contains roughly nodes, so the space complexity simplifies to .

The following resource provides a concise summary of this analysis.

Level Order Traversal of a Binary Tree in Java

This GeeksforGeeks article has a dedicated section explaining the performance of the algorithm.

Please find the heading "Complexity of the above Method" and read the short explanation for time and space complexity. This formalizes the reasoning behind the O(n) performance.

Conclusion

Congratulations on mastering tree traversals! You have now implemented both depth-first and breadth-first search algorithms for binary trees, two of the most fundamental graph traversal techniques. While DFS (using recursion) is often elegant for problems involving paths and hierarchical structure, BFS (using a queue) is the go-to for finding shortest paths and exploring layer by layer.

Key Takeaways:

  • Level-order traversal is an application of Breadth-First Search (BFS) on a tree.
  • It explores the tree level by level, from left to right.
  • The implementation is iterative and relies on a Queue to maintain the order of nodes to visit, leveraging its FIFO property.
  • The time complexity is , as each node is visited once.
  • The space complexity is in the worst case, determined by the maximum width of the tree.

This lesson concludes our module on core data structures. You've built a solid foundation in recursion, linked lists, hash maps, and tree traversals. In our next module, we will shift gears significantly and enter the world of Java Concurrency. You'll learn how to create and manage multiple threads, a critical skill for building the high-performance, responsive backend applications that are your ultimate goal.