Queue-based

Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
  int size = q.size();
  List level = new ArrayList<>();
  for (int i = 0; i < size; i++) {
    Node n = q.poll();
    level.add(n.val);
    if (n.left != null) q.offer(n.left);
    if (n.right != null) q.offer(n.right);
  }
  result.add(level);
}
Advertisement

Complexity

O(N) time. O(W) space where W = max width of tree.

Advertisement

Zigzag variant

Alternate directions per level: L→R, R→L. Reverse level list on odd rows.

Bottom-up

Same BFS. Reverse result list at end. Or collect levels then reverse.