DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Binary Tree Level Order Traversal

mediumTrees Must-do

Problem statement

Given the root of a binary tree, return its values grouped by level: a list whose first entry holds the root's value, the second entry holds the values one level down, and so on. Within a level, list values from left to right.

An empty tree gives an empty list. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [8, 4, 12, 2, 6, null, 14]

Output: [[8], [4, 12], [2, 6, 14]]

Example 2

Input: root = [5, null, 7, 6]

Output: [[5], [7], [6]]

Explanation: Each level has a single node.

Hints

Approach

Use a breadth-first search with a queue, and process the queue one level at a time.

  1. If the root is empty, return [].
  2. Put the root in a queue.
  3. While the queue is not empty: read its size k. Pop exactly k nodes, add their values to a new level list, and push their children.
  4. Append the level list to the result.

The size read in step 3 is taken before any children are added, so it covers exactly the current level. Each node is pushed and popped once.

ComplexityTime O(n)Space O(w), where w is the widest level
Python
from collections import deque
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: Optional["TreeNode"]) -> list[list[int]]:
if root is None:
return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # size fixed before children are added
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result

Follow-up questions

  • Return the levels bottom-up, or in zigzag order (left to right, then right to left).
  • Return the average value of each level.

Frequently asked questions

Children are pushed onto the same queue while you process the level. If you checked the size on every iteration, the loop would keep going into the next level. Capturing it first draws the boundary.

Yes. Pass depth into a recursive walk. If depth == len(result), append a new empty list, then append the value to result[depth]. Visiting left before right keeps each level in left-to-right order. It is O(n) time and O(h) stack.

Breadth-first order is how you roll changes out in waves: first the root, then every direct dependant, then the next ring. It is also how you find everything within N hops of a host, or group an org chart or dependency tree by distance.