BeginnerTrees

Tree BFS

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

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

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.

General Recognition Cues
General indicators that this pattern might be applicable
  • Level order
  • Per-level aggregation
  • Connect next pointers
  • Right/left view
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
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
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