CodeMosa

Master LeetCode Patterns

BeginnerTreesRead Trees Fundamentals →

Tree BFS

Level-order traversal patterns: standard, zigzag, right view, and connecting next pointers

Time: O(n)
Space: O(w)

What is Tree BFS?

#
Definition: Traverse the tree level by level using a queue to compute per-level results and views.

Core Idea

#

Use a queue to process nodes by levels and track boundaries to derive level-based properties.

When to Use

#

Use when output depends on levels, sibling connections, or views from one side.

How Tree BFS works

#

Queue-based level traversal with level-size boundaries for per-level aggregation, zigzag order, side views, and sibling connections.

  • Level order
  • Per-level aggregation
  • Connect next pointers

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Level order
  • Per-level aggregation
  • Connect next pointers
  • Right/left view

Code Templates

#
Queue-based level traversal with level-size boundaries for per-level aggregation, zigzag order, side views, and sibling connections.
# Tree BFS (Level Order) Template
from collections import deque

def level_order(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        size=len(q); level=[]
        for _ in range(size):
            n=q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

Level Order

#

Collect nodes level by level

When to Use This Variant
  • Queue + level size
Use Case
Level lists
Advantages
  • Simple
  • Deterministic
Implementation
from collections import deque
def level_order(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        size = len(q); level = []
        for _ in range(size):
            node = q.popleft(); level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res
2

Zigzag

#

Alternate direction per level

When to Use This Variant
  • Reverse every other level
Use Case
Zigzag traversal
Advantages
  • Minor variant of BFS
Implementation
from collections import deque
def zigzag_level_order(root):
    if not root: return []
    res, q, ltr = [], deque([root]), True
    while q:
        size = len(q); level = deque()
        for _ in range(size):
            node = q.popleft()
            (level.append if ltr else level.appendleft)(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(list(level)); ltr = not ltr
    return res
3

Right View

#

Track last node per level

When to Use This Variant
  • Rightmost per level
Use Case
Side views
Advantages
  • O(n)
  • One pass
Implementation
from collections import deque
def right_side_view(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        size = len(q)
        for i in range(size):
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
            if i == size - 1: res.append(node.val)
    return res
4

Connect Next Pointers

#

Link siblings using level BFS

When to Use This Variant
  • Populate next
Use Case
Perfect/any binary trees
Advantages
  • Queue or O(1) perfect tree
Implementation
from collections import deque
def connect_next(root):
    if not root: return root
    q = deque([root])
    while q:
        prev = None
        for _ in range(len(q)):
            node = q.popleft()
            if prev: prev.next = node
            prev = node
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        prev.next = None
    return root

Common Pitfalls

#
Watch out for these common mistakes
  • Forgetting level size boundary
  • Null child checks
  • Mixing levels when enqueuing

Related Patterns

#
BST OperationsLowest Common AncestorTree DFS (Depth-First Search)Trie

Example Problems

#
Classic LeetCode problems using this pattern

Complexity Analysis

#
Time Complexity
O(n)

Each node visited once.

Space Complexity
O(w)

Queue holds up to width w of a level.

Ready to test your knowledge?

Test your pattern recognition with interactive questions