Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Medium

Binary Tree Level Order Traversal

Binary tree level order traversal explained: BFS with a queue, grouping nodes level by level, tested Python code, common mistakes and a live tree visual.

Also searched as: BFS on a binary tree · print tree level by level · level order traversal using a queue

🌳

Try it live Free

Binary Search Tree & Traversals

In the BST lab, run level-order and watch the walk sweep the tree row by row, unlike the three depth-first orders.

Also useful: Graph Search: BFS vs DFS

Open the playground →

The problem

Given the root of a binary tree, return its node values level by level, from top to bottom and left to right within each level, as a list of lists.

Inputroot = [3, 9, 20, null, null, 15, 7]
Output[[3], [9, 20], [15, 7]]

The key insight

Depth-first walks dive down one branch, but here you want the tree in rings by distance from the root, which is exactly what breadth-first search with a queue produces. The trick for grouping is to read the queue's length at the start of each round: exactly that many nodes belong to the current level.

Brute force first: You could compute every node's depth with DFS and bucket values by depth; it works in O(n) too, but BFS states the idea more directly.

Step-by-step approach

  1. If the root is empty, return an empty list.
  2. Put the root in a queue (collections.deque).
  3. While the queue is not empty, read size = len(queue): that is the number of nodes on this level.
  4. Pop exactly size nodes, record their values in a level list, and push their non-null children.
  5. Append the level list to the answer and repeat.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

from collections import deque


def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # nodes currently queued = one level
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(level)
    return out

Complexity

TimeO(n)
SpaceO(w)

Each node is enqueued and dequeued once. The queue holds at most one level at a time, so extra space is the maximum width w of the tree, up to about n/2 for a complete tree.

Common mistakes

Frequently asked questions

What is the time and space complexity of level order traversal?

O(n) time since every node is processed once, and O(w) space for the queue, where w is the widest level. For a complete binary tree that is about n/2, so O(n) in the worst case.

How do I return the levels in zigzag order?

Run the same BFS and reverse every other level list before appending it, or use a deque and append values to alternate ends. The traversal itself does not change.

Can level order be done with DFS?

Yes. Pass the depth into a recursive DFS and append each value to out[depth], creating a new list when depth equals len(out). Visiting left before right keeps the left-to-right order.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.