#33 · Trees

Binary Tree Level Order Traversal

Given the root of a binary tree, return the values of its nodes level by level, from left to right, as a list of lists.

MediumLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Queue (FIFO)

First in, first out. Nodes are added at the back and taken from the front, so nodes discovered earlier (shallower ones) are visited before nodes discovered later (deeper ones). That is exactly breadth-first order.

Memory layout

A circular buffer or linked list in real deques. A plain array used as a queue needs a head index (or two arrays), because removing from the front of an array shifts every element.

Operation	Cost
enqueue / dequeue	O(1) (with a head index or deque)
whole traversal	O(n) time, O(w) space for the widest level w

Level boundary (size snapshot or frontier swap)

A queue alone interleaves levels. Fixing size = queue length at the start of a level (or giving each level its own array) tells you where one level ends and the next begins.

Memory layout

One integer, or one extra array of the next level.

Operation	Cost
separate levels	O(1) per level

Why it fits

Breadth-first order is "nearest to the root first", which is exactly what a FIFO queue gives for free: children are enqueued behind everything already waiting.
Grouping by level only needs to know how many nodes the queue held when the level began; everything enqueued after that belongs to the next level.
Every node is enqueued and dequeued exactly once, so O(n) time is optimal.

Why alternatives degrade

DFS without a level number:: DFS visits depth-first, so values of one level are scattered across the traversal. Carrying the level number (and appending into result[level]) fixes it, at the cost of recursion depth.
One DFS per level:: Re-walks the tree from the root for every level: O(n·h).
Array with shift() as a queue:: Each shift is O(n), so the whole traversal can become O(n²).

Four approaches, from naive to production

1 · beginner

One DFS per level

time O(n·h)space O(h)

Compute the tree height h. For each level from 0 to h − 1, walk the tree from the root and collect the nodes exactly that deep.

int height(TreeNode* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }

void collect(TreeNode* node, int level, vector<int>& out) {
    if (!node) return;
    if (level == 0) { out.push_back(node->val); return; }
    collect(node->left, level - 1, out);
    collect(node->right, level - 1, out);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    int h = height(root);
    for (int level = 0; level < h; level++) {
        vector<int> vals;
        collect(root, level, vals);
        result.push_back(vals);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    int h = height(root);
    for (int level = 0; level < h; level++) {
        List<Integer> vals = new ArrayList<>();
        collect(root, level, vals);
        result.add(vals);
    }
    return result;
}

private int height(TreeNode n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }

private void collect(TreeNode node, int level, List<Integer> out) {
    if (node == null) return;
    if (level == 0) { out.add(node.val); return; }
    collect(node.left, level - 1, out);
    collect(node.right, level - 1, out);
}

def level_order(root):
    result = []
    h = height(root)
    for level in range(h):
        vals = []
        collect(root, level, vals)
        result.append(vals)
    return result

def height(node):
    return 1 + max(height(node.left), height(node.right)) if node else 0

def collect(node, level, out):
    if not node: return
    if level == 0:
        out.append(node.val)
        return
    collect(node.left, level - 1, out)
    collect(node.right, level - 1, out)

function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  const h = height(root);
  for (let level = 0; level < h; level++) {
    const vals: number[] = [];
    collect(root, level, vals);
    result.push(vals);
  }
  return result;
}

function height(node: TreeNode | null): number {
  return node ? 1 + Math.max(height(node.left), height(node.right)) : 0;
}

function collect(node: TreeNode | null, level: number, out: number[]): void {
  if (!node) return;
  if (level === 0) { out.push(node.val); return; }
  collect(node.left, level - 1, out);
  collect(node.right, level - 1, out);
}

Flaws & bottlenecks

Re-walks the upper levels of the tree for every level: O(n·h), which is O(n²) on a skewed tree.
Needs the height first (another full pass).
Does not use a queue, so the "level order" is recomputed instead of discovered.

Interviewer cross-questions

Why is it O(n·h)?

Say: collect() for level k visits every node above level k and the nodes of level k, which is up to n nodes, and it runs h times.

When would you still choose it?

Say: Almost never: it is a teaching step. It shows why a single pass that remembers the level (BFS or a DFS that carries the depth) is better.

How can one pass produce the same result?

Say: Pass the level down in a DFS and append into result[level], or use a queue and process one level at a time.

2 · intermediate

DFS carrying the level

time O(n)space O(h)

Recurse with (node, level). The first time a level is reached, create its list; then append the node to result[level]. Visiting left before right keeps each level in left-to-right order.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int level) {
        if (!node) return;
        if ((int)result.size() == level) result.push_back({});
        result[level].push_back(node->val);
        dfs(node->left, level + 1);
        dfs(node->right, level + 1);
    };
    dfs(root, 0);
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, 0, result);
    return result;
}

private void dfs(TreeNode node, int level, List<List<Integer>> result) {
    if (node == null) return;
    if (result.size() == level) result.add(new ArrayList<>());
    result.get(level).add(node.val);
    dfs(node.left, level + 1, result);
    dfs(node.right, level + 1, result);
}

def level_order(root):
    result = []
    def dfs(node, level):
        if not node: return
        if len(result) == level: result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  const dfs = (node: TreeNode | null, level: number): void => {
    if (!node) return;
    if (result.length === level) result.push([]);
    result[level].push(node.val);
    dfs(node.left, level + 1);
    dfs(node.right, level + 1);
  };
  dfs(root, 0);
  return result;
}

Flaws & bottlenecks

Uses recursion, so a very deep tree overflows the call stack.
It is not really a breadth-first traversal: nodes are produced in DFS order and only grouped by level afterwards.
The "create the list on the first visit" check relies on levels being reached in increasing order of first appearance, which holds for DFS but is easy to break.

Interviewer cross-questions

Why does each level come out in left-to-right order?

Say: DFS visits the left subtree completely before the right one, so within one level the left nodes are always appended before the right nodes.

Why is result.length === level the right test for a new level?

Say: Levels are first reached in order 0, 1, 2, … (to reach level k you pass through level k−1), so when level == result.length, the list for this level does not exist yet.

Can a tall tree break this?

Say: Yes, the recursion depth is the tree height. BFS with a queue does not recurse and its memory is the width instead.

3 · advanced

BFS with a queue and level size

time O(n)space O(w)

Keep a queue of waiting nodes. At the start of each level take size = number waiting, process exactly that many (collecting values and enqueuing children), then store the level.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    vector<TreeNode*> queue = {root};
    size_t head = 0;
    while (head < queue.size()) {
        int size = queue.size() - head;
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = queue[head++];
            level.push_back(node->val);
            if (node->left) queue.push_back(node->left);
            if (node->right) queue.push_back(node->right);
        }
        result.push_back(level);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<TreeNode> queue = new ArrayList<>(); queue.add(root);
    int head = 0;
    while (head < queue.size()) {
        int size = queue.size() - head;
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.get(head++);
            level.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(level);
    }
    return result;
}

def level_order(root):
    if not root: return []
    result = []
    queue = [root]
    head = 0
    while head < len(queue):
        size = len(queue) - head
        level = []
        for _ in range(size):
            node = queue[head]
            head += 1
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0;
  while (head < queue.length) {
    const size = queue.length - head;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Flaws & bottlenecks

The queue can hold a whole level: O(n/2) for a full tree.
The head index means the array only ever grows (it keeps already-visited nodes); a real deque would free them.
Capturing size before the loop is easy to forget, which silently merges levels.

Interviewer cross-questions

Why capture size before the inner loop?

Say: The queue grows as children are enqueued. Without the snapshot the loop would keep consuming the next level as well, and the levels would run together.

How would you get a zigzag (right-to-left on alternate levels) order?

Say: Collect each level as usual and reverse every other level (or insert at the front for odd levels). The traversal itself does not change.

What is the memory use?

Say: The queue holds at most two adjacent levels, so O(width). For a balanced tree that is about n/2 nodes, much more than the O(log n) a DFS needs.

4 · expert

Two arrays: frontier and next

time O(n)space O(w)

Hold the current level in an array and build the next level in a second array, then swap. No head index, no size counter, no removal from the front.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    vector<TreeNode*> frontier = {root};
    while (!frontier.empty()) {
        vector<TreeNode*> next;
        vector<int> vals;
        for (TreeNode* node : frontier) {
            vals.push_back(node->val);
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        result.push_back(vals);
        frontier = next;
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<TreeNode> frontier = new ArrayList<>(); frontier.add(root);
    while (!frontier.isEmpty()) {
        List<TreeNode> next = new ArrayList<>();
        List<Integer> vals = new ArrayList<>();
        for (TreeNode node : frontier) {
            vals.add(node.val);
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        result.add(vals);
        frontier = next;
    }
    return result;
}

def level_order(root):
    if not root: return []
    result = []
    frontier = [root]
    while frontier:
        next_level = []
        vals = []
        for node in frontier:
            vals.append(node.val)
            if node.left: next_level.append(node.left)
            if node.right: next_level.append(node.right)
        result.append(vals)
        frontier = next_level
    return result

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  let frontier: TreeNode[] = [root];
  while (frontier.length > 0) {
    const next: TreeNode[] = [];
    const vals: number[] = [];
    for (const node of frontier) {
      vals.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    result.push(vals);
    frontier = next;
  }
  return result;
}

Flaws & bottlenecks

Allocates a new array for every level (garbage), though total allocation is still O(n).
Keeps only one level at a time, so it cannot easily compute things that need the whole queue (like "right side view" is fine, but "next pointers across levels" needs care).
Slightly less familiar than the classic queue loop.

Interviewer cross-questions

Why is this nicer than a queue?

Say: Level boundaries are implicit: the array IS the level. There is no size snapshot to forget and no O(n) shift, and iterating with for...of is cache friendly.

How would you reuse the arrays to avoid allocation?

Say: Keep two preallocated buffers and swap them, resetting the length of the old one to 0 each level (the same trick as double buffering).

What if the tree is huge but shallow?

Say: Then the frontier is large: memory O(w) is unavoidable for level-order. A DFS that carries the level uses far less memory but needs recursion (or an explicit stack) and builds levels out of order.

Synchronized code walkthrough

Showing: One DFS per level — shares the player above; click any step to jump.

int height(TreeNode* n) { return n ? 1 + max(height(n->left), height(n->right)) : 0; }

void collect(TreeNode* node, int level, vector<int>& out) {
    if (!node) return;
    if (level == 0) { out.push_back(node->val); return; }
    collect(node->left, level - 1, out);
    collect(node->right, level - 1, out);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    int h = height(root);
    for (int level = 0; level < h; level++) {
        vector<int> vals;
        collect(root, level, vals);
        result.push_back(vals);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    int h = height(root);
    for (int level = 0; level < h; level++) {
        List<Integer> vals = new ArrayList<>();
        collect(root, level, vals);
        result.add(vals);
    }
    return result;
}

private int height(TreeNode n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }

private void collect(TreeNode node, int level, List<Integer> out) {
    if (node == null) return;
    if (level == 0) { out.add(node.val); return; }
    collect(node.left, level - 1, out);
    collect(node.right, level - 1, out);
}

def level_order(root):
    result = []
    h = height(root)
    for level in range(h):
        vals = []
        collect(root, level, vals)
        result.append(vals)
    return result

def height(node):
    return 1 + max(height(node.left), height(node.right)) if node else 0

def collect(node, level, out):
    if not node: return
    if level == 0:
        out.append(node.val)
        return
    collect(node.left, level - 1, out)
    collect(node.right, level - 1, out)

function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  const h = height(root);
  for (let level = 0; level < h; level++) {
    const vals: number[] = [];
    collect(root, level, vals);
    result.push(vals);
  }
  return result;
}

function height(node: TreeNode | null): number {
  return node ? 1 + Math.max(height(node.left), height(node.right)) : 0;
}

function collect(node: TreeNode | null, level: number, out: number[]): void {
  if (!node) return;
  if (level === 0) { out.push(node.val); return; }
  collect(node.left, level - 1, out);
  collect(node.right, level - 1, out);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int level) {
        if (!node) return;
        if ((int)result.size() == level) result.push_back({});
        result[level].push_back(node->val);
        dfs(node->left, level + 1);
        dfs(node->right, level + 1);
    };
    dfs(root, 0);
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, 0, result);
    return result;
}

private void dfs(TreeNode node, int level, List<List<Integer>> result) {
    if (node == null) return;
    if (result.size() == level) result.add(new ArrayList<>());
    result.get(level).add(node.val);
    dfs(node.left, level + 1, result);
    dfs(node.right, level + 1, result);
}

def level_order(root):
    result = []
    def dfs(node, level):
        if not node: return
        if len(result) == level: result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

function levelOrder(root: TreeNode | null): number[][] {
  const result: number[][] = [];
  const dfs = (node: TreeNode | null, level: number): void => {
    if (!node) return;
    if (result.length === level) result.push([]);
    result[level].push(node.val);
    dfs(node.left, level + 1);
    dfs(node.right, level + 1);
  };
  dfs(root, 0);
  return result;
}

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    vector<TreeNode*> queue = {root};
    size_t head = 0;
    while (head < queue.size()) {
        int size = queue.size() - head;
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = queue[head++];
            level.push_back(node->val);
            if (node->left) queue.push_back(node->left);
            if (node->right) queue.push_back(node->right);
        }
        result.push_back(level);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<TreeNode> queue = new ArrayList<>(); queue.add(root);
    int head = 0;
    while (head < queue.size()) {
        int size = queue.size() - head;
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.get(head++);
            level.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        result.add(level);
    }
    return result;
}

def level_order(root):
    if not root: return []
    result = []
    queue = [root]
    head = 0
    while head < len(queue):
        size = len(queue) - head
        level = []
        for _ in range(size):
            node = queue[head]
            head += 1
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0;
  while (head < queue.length) {
    const size = queue.length - head;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    vector<TreeNode*> frontier = {root};
    while (!frontier.empty()) {
        vector<TreeNode*> next;
        vector<int> vals;
        for (TreeNode* node : frontier) {
            vals.push_back(node->val);
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        result.push_back(vals);
        frontier = next;
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<TreeNode> frontier = new ArrayList<>(); frontier.add(root);
    while (!frontier.isEmpty()) {
        List<TreeNode> next = new ArrayList<>();
        List<Integer> vals = new ArrayList<>();
        for (TreeNode node : frontier) {
            vals.add(node.val);
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        result.add(vals);
        frontier = next;
    }
    return result;
}

def level_order(root):
    if not root: return []
    result = []
    frontier = [root]
    while frontier:
        next_level = []
        vals = []
        for node in frontier:
            vals.append(node.val)
            if node.left: next_level.append(node.left)
            if node.right: next_level.append(node.right)
        result.append(vals)
        frontier = next_level
    return result

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  let frontier: TreeNode[] = [root];
  while (frontier.length > 0) {
    const next: TreeNode[] = [];
    const vals: number[] = [];
    for (const node of frontier) {
      vals.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    result.push(vals);
    frontier = next;
  }
  return result;
}