Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

BFS & Level Order
DSA

BFS & Level Order

Understand how queues enable level-by-level traversal and processing of trees.

BFS (Level Order) traverses a tree level by level, processing all nodes at the same depth before moving deeper.

Its core advantage:

BFS guarantees the shortest path in unweighted trees and enables level-aware problems.

Focus on recognizing:

“Level by level” + “Queue” + “Breadth” = BFS / Level Order

Pattern Table

PatternTypical QuestionsTrigger
Level OrderReturn levels as listsQueue + size batching
Right/Left ViewSee first node at each levelTrack first/last in level
ZigzagAlternating left-rightToggle direction per level

Mental Trigger

Queue → Process level size → Add children → Repeat.

1. Generic Java BFS Template (Base)

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
    }

    return result;
}
from collections import deque

def level_order(root):
    result = []
    if root is None:
        return result

    queue = deque([root])

    while queue:
        size = len(queue)
        level = []

        for _ in range(size):
            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
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        vector<int> level;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }

        result.push_back(level);
    }

    return result;
}
function levelOrder(root) {
  const result = [];
  if (root === null) return result;

  const queue = [root];

  while (queue.length > 0) {
    const size = queue.length;
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}

Everything else in Level Order is just a modification of this template.

Pattern 1: Right Side View

Last node dequeued per level = what you see from the right. Press ▶ to animate.

Right Side View

Return the last node visible on each level when the tree is viewed from the right.

BFS level by level using a queue; the final node dequeued in each level is exactly the rightmost node. No depth-tracking DFS needed.

TREE VISUALIZER
Steps –
12354
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        queue = [root]
                      
                        2
                        while queue:
                      
                        3
                          size = len(queue)          // level marker
                      
                        4
                          for i in 0..size-1:
                      
                        5
                            n = dequeue; if i == size-1 → visible
                      
                        6
                            enqueue children

Java Code

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (i == size - 1)
                result.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    return result;
}
def right_side_view(root):
    result = []
    if root is None:
        return result

    queue = deque([root])

    while queue:
        size = len(queue)

        for i in range(size):
            node = queue.popleft()

            if i == size - 1:
                result.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result
vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (i == size - 1)
                result.push_back(node->val);

            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
    }

    return result;
}
function rightSideView(root) {
  const result = [];
  if (root === null) return result;

  const queue = [root];

  while (queue.length > 0) {
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();

      if (i === size - 1)
        result.push(node.val);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
  }

  return result;
}

What Changed from the Base Template?

Track last node in each level

Base:

level.add(node.val); // add all nodes

Changed:

if (i == size - 1)
    result.add(node.val); // only add last node of level

because the right side view is the last (rightmost) node at each level.

Right Side View = Level Order + Add last node of each level.

Pattern 2: Zigzag Level Order

Same level BFS with a direction flag that flips each row. Press ▶ to animate.

Zigzag Level Order

Return tree values level by level, alternating left-to-right and right-to-left each row.

Standard BFS collects each level, then reverse the level when the direction flag is false and toggle it. Same skeleton as right-side view — only the per-level bookkeeping differs.

TREE VISUALIZER
Steps –
3920157
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        BFS by levels
                      
                        2
                        leftToRight = true
                      
                        3
                        collect level values
                      
                        4
                        if !leftToRight: reverse(level)
                      
                        5
                        toggle direction

Java Code

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();

            if (leftToRight)
                level.addLast(node.val);
            else
                level.addFirst(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
        leftToRight = !leftToRight;
    }

    return result;
}
def zigzag_level_order(root):
    result = []
    if root is None:
        return result

    queue = deque([root])
    left_to_right = True

    while queue:
        size = len(queue)
        level = deque()

        for _ in range(size):
            node = queue.popleft()

            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(list(level))
        left_to_right = not left_to_right

    return result
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;

    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;

    while (!q.empty()) {
        int size = q.size();
        deque<int> level;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (leftToRight)
                level.push_back(node->val);
            else
                level.push_front(node->val);

            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }

        result.push_back(vector<int>(level.begin(), level.end()));
        leftToRight = !leftToRight;
    }

    return result;
}
function zigzagLevelOrder(root) {
  const result = [];
  if (root === null) return result;

  const queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const size = queue.length;
    const level = [];

    for (let i = 0; i < size; i++) {
      const node = queue.shift();

      if (leftToRight)
        level.push(node.val);
      else
        level.unshift(node.val);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(level);
    leftToRight = !leftToRight;
  }

  return result;
}

What Changed from the Base Template?

Toggle direction

Added:

boolean leftToRight = true;
// toggle each level
leftToRight = !leftToRight;

because zigzag alternates direction every level.

AddFirst or AddLast

Base:

level.add(node.val);

Changed:

if (leftToRight) level.addLast(node.val);
else level.addFirst(node.val);

to reverse the order of nodes in the level when going right-to-left.

Zigzag = Level Order + Toggle direction + AddFirst for reverse levels.

BFS Pattern Evolution

Base Level Order (queue + size batching)
    ↓
Right Side View
    (+ last node of each level)
    ↓
Zigzag
    (+ toggle direction + addFirst/addLast)

Common Mistakes

Not saving queue.size() before the inner loop.

The size changes as children are added — capture it once at the start.

Forgetting null check.

Always if (root == null) return before creating the queue.

Using poll on empty queue.

Check !queue.isEmpty() before polling.

Recognition Cheat Sheet

If you see…Think…
Level-by-level outputBFS with size batching
Right/left view of treeBFS + track last/first in level
Zigzag / spiral orderBFS + toggle direction
Minimum depthBFS + return when leaf found

My Private Notes

Notes are auto-saved locally to this device.