DSA for Interviews, From Zero

Part 11 · Lesson 42 · read

Level Order (BFS) on Trees

Visit a tree one layer at a time with a queue.

On this page

  1. Level by level
  2. The queue loop
  3. One level at a time
  4. Traced: level order
  5. Why the size snapshot works
  6. Right side view and zigzag
  7. Minimum depth and level averages
  8. Practice questions (7)
  9. Make it stick
  10. What's next

Level by level

Lesson 41 walked trees depth-first: go down one branch, come back, then go down the next. This lesson walks them breadth-first, also called level order. You visit the root, then all of its children, then all of their children, and so on. You go one whole row at a time, like reading a page line by line.

      1          level 0:  1
     / \
    2   3        level 1:  2  3
   / \   \
  4   5   6      level 2:  4  5  6

Breadth-first search (BFS) is a way of walking a tree or graph that visits all nodes at distance 1 from the start, then all nodes at distance 2, and so on. It is the right tool when the question is about rows or how close a node is to the root. For example: print the tree row by row, what do I see from the right side, or what is the shortest path to a leaf. The tool that gives this order is a queue, a first-in, first-out line, like a line at a shop. Nodes join at the back and leave from the front. So the children of a node always wait behind everyone who was found earlier. That keeps the rows in order.

The queue loop

Start with the root in the queue. Then repeat these steps: take a node from the front, visit it, and add its children to the back. Lesson 39 explained why we do not use queue.shift() to take from the front. Removing the first item of a JavaScript array can take time in proportion to the length of the array. A big tree would turn O(n) into O(n²). Instead we keep a number head that marks the front, and we just move it forward. The array only grows. Nothing is removed.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Visit nodes in breadth-first order: the root, then its children, then their children, and so on.function bfs(root) {  if (root === null) return [];  const order = [];  const queue = [root];          // nodes found but not yet visited  let head = 0;                  // the front of the queue (so we avoid the slow shift)  while (head < queue.length) {    const node = queue[head++];  // take from the front    order.push(node.val);    if (node.left) queue.push(node.left);     // add to the back    if (node.right) queue.push(node.right);  }  return order;}console.log(bfs(buildTree([1, 2, 3, 4, 5, null, 6]))); // [1, 2, 3, 4, 5, 6]

Every node enters the queue once and leaves once, so the time is O(n). The extra space is the queue itself. It holds at most about one or two rows of the tree at a time. That is O(w), where w is the number of nodes in the widest row. In a full tree (every row completely filled) the last row holds about half of all the nodes, so w can be about n/2.

Why we say O(w) and not O(h)
The depth-first walks of lesson 41 used space in proportion to the height. BFS uses space in proportion to the width. A long thin chain is cheap for BFS. A wide, bushy tree is cheap for depth-first search. Neither one is always better.

One level at a time

The loop above gives one flat list. Most questions want the rows kept separate. The trick is to save the length of the queue at the start of each round, like taking a photo of it. At that moment the queue holds exactly the nodes of one level and nothing else. So size = queue.length - head tells us how many nodes to process. We process exactly that many. Any children we add during the round wait behind them and belong to the next round.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function levelOrder(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;     // how many nodes are in the current level right now    const level = [];    for (let k = 0; k < size; k++) {      const node = queue[head++];      level.push(node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);  }  return levels;}console.log(levelOrder(buildTree([3, 9, 20, null, null, 15, 7]))); // [[3], [9, 20], [15, 7]]console.log(levelOrder(buildTree([1, 2, 3, 4, 5, null, 6])));      // [[1], [2, 3], [4, 5, 6]]console.log(levelOrder(buildTree([])));                            // []

Traced: level order

Watch the queue (we show only the part not yet visited), the saved size and the level being filled. Notice that size is fixed at the top of each round, even though the queue keeps growing during the round.

step 1 / 19
Set up
queue = [root]

The queue holds nodes we have found but not yet visited. A queue is a line where the first one in is the first one out. We begin with just the root, node 1. head points at the front of the line.

1const levels = [];▶const queue = [root];3let head = 0;4while (head < queue.length) {5  const size = queue.length - head;6  const level = [];7  for (let k = 0; k < size; k++) {8    const node = queue[head++];9    level.push(node.val);10    if (node.left) queue.push(node.left);11    if (node.right) queue.push(node.right);12  }13  levels.push(level);14}
Variables
levels[]
queue[1]
head0
Console
(nothing printed yet)
Three rounds, three rows: [1], then [2, 3], then [4, 5, 6]. Each round starts with a size equal to the number of nodes waiting in the queue. · interactive
Dry run · the queue between rounds
MomentQueue (front on the left)sizeWhat happens
start[1]--
level 1 begins[1]1head moves from 0 to 1; adds 2 and 3
level 2 begins[2, 3]2visit 2 (adds 4 and 5), visit 3 (adds 6)
level 3 begins[4, 5, 6]3no children to add
queue empty[]-done

Between rounds the queue holds exactly one level. This is a rule that always stays true, and the whole technique depends on it.

Why the size snapshot works

Think of the queue as two groups of people standing in a line. The current level is at the front. Behind them are the children added so far. At the start of a round the second group is empty. Each node we process adds its children behind the first group. But the loop stops after size nodes, so it never reaches the newcomers. When the round ends, the front group is gone, and the newcomers become the new "current level". Do not read queue.length inside the loop condition (k < queue.length - head). That is a bug. The number keeps growing as you add children, and the rows get mixed together.

Take the snapshot before the loop
Write const size = queue.length - head once, above the inner loop. Never put the length expression inside the loop condition.

Right side view and zigzag

Once the rows are separate, many questions need only a few lines. A row (or level) is all the nodes that are the same number of steps away from the root. The right side view is what you would see if you stood to the right of the tree. You see the last node of each row. The other nodes in that row are hidden behind it. The zigzag order changes direction each row: row 0 goes left to right, row 1 goes right to left, and so on. We do not need to reverse a row. When a row goes right to left, we write each value straight into its mirror position.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Right side view: the last node of every level is the one you see from the right.function rightSideView(root) {  if (root === null) return [];  const view = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    for (let k = 0; k < size; k++) {      const node = queue[head++];      if (k === size - 1) view.push(node.val);   // the rightmost node of this level      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }  }  return view;}// Zigzag: level 0 left to right, level 1 right to left, level 2 left to right, ...function zigzagLevelOrder(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  let leftToRight = true;  while (head < queue.length) {    const size = queue.length - head;    const level = new Array(size);    for (let k = 0; k < size; k++) {      const node = queue[head++];      level[leftToRight ? k : size - 1 - k] = node.val;   // write to the mirror position on odd levels      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);    leftToRight = !leftToRight;  }  return levels;}const tree = buildTree([1, 2, 3, 4, null, null, 5]);console.log(rightSideView(tree));       // [1, 3, 5]console.log(zigzagLevelOrder(buildTree([3, 9, 20, null, null, 15, 7]))); // [[3], [20, 9], [15, 7]]

Minimum depth and level averages

Minimum depth is the number of nodes on the shortest path from the root to a leaf (a node with no children). BFS goes through the tree from the top down. So the first leaf it meets is the closest one to the top, and it can return at once without looking at the rest of the tree. A depth-first search may have to look at much more of the tree before it knows the answer.

A node with one child is not a leaf
For a chain like [2, null, 3] the answer is 2, not 1. The root has a right child, so it is not a leaf. The only leaf is 3. The simple recursion 1 + Math.min(depth(left), depth(right)) gets this wrong, because the missing side counts as depth 0. Only a node with both children missing ends a path.

Level averages show another benefit of saving the size. We know how many nodes are in a row, so we can divide the sum of the row by that number.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Minimum depth: the number of nodes on the shortest path from the root to a LEAF.// BFS reaches the closest leaf (nearest the top) first, so it can stop as soon as it sees one.function minDepth(root) {  if (root === null) return 0;  const queue = [root];  let head = 0;  let depth = 1;  while (head < queue.length) {    const size = queue.length - head;    for (let k = 0; k < size; k++) {      const node = queue[head++];      if (node.left === null && node.right === null) return depth;   // first leaf found = closest to the top      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    depth++;  }  return depth;}// Average of each level.function averageOfLevels(root) {  if (root === null) return [];  const averages = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    let sum = 0;    for (let k = 0; k < size; k++) {      const node = queue[head++];      sum += node.val;      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    averages.push(sum / size);  }  return averages;}console.log(minDepth(buildTree([3, 9, 20, null, null, 15, 7])));        // 2console.log(minDepth(buildTree([2, null, 3, null, 4, null, 5, null, 6]))); // 5console.log(averageOfLevels(buildTree([3, 9, 20, 15, 7])));              // [3, 14.5, 11]

Practice questions

For each question, ask two things. Do I need the rows kept separate? And what do I keep from each row: all of it, the last node, the sum, or the maximum?

Q1Binary tree level order traversalMedium

Return the level order traversal of a binary tree: a list of rows from the top row down, with each row read left to right.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Explanation: Row 0 is the root. Row 1 is its two children. Row 2 is the children of 20.
Example 2
Input: root = [1]
Output: [[1]]
Explanation: One node, one row.
Example 3
Input: root = []
Output: []
Explanation: There are no rows at all (not even one empty row).
Stuck? Open one hint at a time
Hint 1
A queue gives you the nodes in the right order. How do you know where one row ends and the next row begins?
Hint 2
At the start of each round the queue holds exactly one row. Count how many nodes it has.
Hint 3
Another way: a depth-first walk that carries the depth can put each value straight into levels[depth].
Show all 3 solutions with explanations
Approach 1Depth-first, passing the depth
The idea

Walk the tree with recursion (a function that calls itself) and pass the current depth along. If levels has no array for this depth yet, add one. Push the value of the node into levels[depth]. Go left before right, so each row stays in left-to-right order.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function levelOrder(root) {  const levels = [];  function walk(node, depth) {    if (node === null) return;    if (levels.length === depth) levels.push([]);    levels[depth].push(node.val);    walk(node.left, depth + 1);    walk(node.right, depth + 1);  }  walk(root, 0);  return levels;}console.log(levelOrder(buildTree([3, 9, 20, null, null, 15, 7]))); // [[3], [9, 20], [15, 7]]console.log(levelOrder(buildTree([1])));                          // [[1]]console.log(levelOrder(buildTree([])));                           // []
How it works

O(n) time, and O(h) space for the call stack (the pile of open calls) plus the output. It works because nodes at the same depth are met from left to right. It is not really BFS, but it gives the same rows.

Approach 2BFS with a saved size
The idea
  1. Put the root in a queue. Keep a head number that marks the front.
  2. While the queue is not empty, let size = queue.length - head.
  3. Take size nodes from the front. Put their values into one row, and add their children to the queue.
  4. Add the row to the answer.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function levelOrder(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    const level = [];    for (let k = 0; k < size; k++) {      const node = queue[head++];      level.push(node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);  }  return levels;}console.log(levelOrder(buildTree([3, 9, 20, null, null, 15, 7]))); // [[3], [9, 20], [15, 7]]console.log(levelOrder(buildTree([1])));                          // [[1]]console.log(levelOrder(buildTree([])));                           // []
How it works

O(n) time. O(w) space for the queue, where w is the number of nodes in the widest row. This is the pattern for the rest of the lesson.

Approach 3Two arrays: current row and next row
The idea

Instead of one queue, keep the current row as an array. Build the next row by collecting the children of every node in it, then swap the two. You do not need a size or a head number.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function levelOrder(root) {  if (root === null) return [];  const levels = [];  let current = [root];  while (current.length > 0) {    levels.push(current.map((node) => node.val));    const next = [];    for (const node of current) {      if (node.left) next.push(node.left);      if (node.right) next.push(node.right);    }    current = next;  }  return levels;}console.log(levelOrder(buildTree([3, 9, 20, null, null, 15, 7]))); // [[3], [9, 20], [15, 7]]console.log(levelOrder(buildTree([1])));                          // [[1]]console.log(levelOrder(buildTree([])));                           // []
How it works

O(n) time, O(w) space. It is easy to read, and a good fit when you need the whole row as an array anyway.

Which approach should you use?

Learn the saved-size BFS by heart. Every other BFS question is a small change to it. (LeetCode 102.)

Q2Binary tree right side viewMedium

Imagine you stand on the right side of a binary tree. Return the values of the nodes you can see, from top to bottom.

Example 1
Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]
Explanation: Row 2 holds 5 and 4. Node 4 is the rightmost, so it hides 5.
Example 2
Input: root = [1, 2, 3, 4, null, null, null, 5]
Output: [1, 3, 4, 5]
Explanation: Row 2 has only 4 and row 3 has only 5, so both can be seen.
Example 3
Input: root = [1, null, 3]
Output: [1, 3]
Explanation: There is a single path to the right.
Example 4
Input: root = []
Output: []
Explanation: There is nothing to see.
Stuck? Open one hint at a time
Hint 1
Which node of each row is visible from the right?
Hint 2
It does not have to be a right child. In the second example, 4 is a left child, but it is the only node in its row.
Show all 3 solutions with explanations
Approach 1Full level order, then take the last of each row
The idea

Build every row as in the last question. Keep the last value of each row.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function rightSideView(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    const level = [];    for (let k = 0; k < size; k++) {      const node = queue[head++];      level.push(node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);  }  return levels.map((level) => level[level.length - 1]);}console.log(rightSideView(buildTree([1, 2, 3, null, 5, null, 4])));            // [1, 3, 4]console.log(rightSideView(buildTree([1, 2, 3, 4, null, null, null, 5])));      // [1, 3, 4, 5]console.log(rightSideView(buildTree([])));                                     // []
How it works

O(n) time. It stores every value, even though we need only one per row.

Approach 2BFS keeping only the last node of each row
The idea

With the saved size, the node at position k === size - 1 is the last of its row. Record only that one.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function rightSideView(root) {  if (root === null) return [];  const view = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    for (let k = 0; k < size; k++) {      const node = queue[head++];      if (k === size - 1) view.push(node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }  }  return view;}console.log(rightSideView(buildTree([1, 2, 3, null, 5, null, 4])));            // [1, 3, 4]console.log(rightSideView(buildTree([1, 2, 3, 4, null, null, null, 5])));      // [1, 3, 4, 5]console.log(rightSideView(buildTree([1, null, 3])));                           // [1, 3]console.log(rightSideView(buildTree([])));                                     // []
How it works

O(n) time, O(w) space.

Approach 3Depth-first, right child first
The idea

Visit the right child before the left child. Then the first node you reach at each new depth is the rightmost one in its row. You know it is a new depth when depth === view.length.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function rightSideView(root) {  const view = [];  function walk(node, depth) {    if (node === null) return;    if (depth === view.length) view.push(node.val);   // first time we reach this depth    walk(node.right, depth + 1);    walk(node.left, depth + 1);  }  walk(root, 0);  return view;}console.log(rightSideView(buildTree([1, 2, 3, null, 5, null, 4])));            // [1, 3, 4]console.log(rightSideView(buildTree([1, 2, 3, 4, null, null, null, 5])));      // [1, 3, 4, 5]console.log(rightSideView(buildTree([])));                                     // []
How it works

O(n) time, O(h) space, which is better than BFS for a wide tree. Remember this trick: the length of the answer tells you the deepest depth seen so far.

Which approach should you use?

Use either of the last two. BFS shows that you understand rows. Depth-first uses less memory for bushy trees. (LeetCode 199.)

Q3Binary tree zigzag level order traversalMedium

Return the zigzag level order traversal: the first row left to right, the next row right to left, and so on, switching each time.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]
Explanation: Row 1 is read from right to left. Row 2 goes back to left to right.
Example 2
Input: root = [1]
Output: [[1]]
Explanation: One row.
Example 3
Input: root = []
Output: []
Explanation: No rows.
Stuck? Open one hint at a time
Hint 1
The order in which you visit the nodes stays the same. Only the way you store each row changes.
Hint 2
Keep a true/false value (a boolean) that flips after every row.
Show all 3 solutions with explanations
Approach 1Level order, then reverse every other row
The idea

Build the rows normally. Reverse the rows at odd indices at the end.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function zigzagLevelOrder(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    const level = [];    for (let k = 0; k < size; k++) {      const node = queue[head++];      level.push(node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);  }  for (let i = 1; i < levels.length; i += 2) levels[i].reverse();  return levels;}console.log(zigzagLevelOrder(buildTree([3, 9, 20, null, null, 15, 7])));      // [[3], [20, 9], [15, 7]]console.log(zigzagLevelOrder(buildTree([1, 2, 3, 4, null, null, 5])));         // [[1], [3, 2], [4, 5]]console.log(zigzagLevelOrder(buildTree([])));                                  // []
How it works

O(n) time. Each reversal takes time in proportion to the row, so the total is still O(n). This is the easiest one to get right.

Approach 2Write into the mirror position
The idea

You know the row size in advance, so create new Array(size). On right-to-left rows, put the k-th visited node at index size - 1 - k.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function zigzagLevelOrder(root) {  if (root === null) return [];  const levels = [];  const queue = [root];  let head = 0;  let leftToRight = true;  while (head < queue.length) {    const size = queue.length - head;    const level = new Array(size);    for (let k = 0; k < size; k++) {      const node = queue[head++];      level[leftToRight ? k : size - 1 - k] = node.val;      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    levels.push(level);    leftToRight = !leftToRight;  }  return levels;}console.log(zigzagLevelOrder(buildTree([3, 9, 20, null, null, 15, 7])));      // [[3], [20, 9], [15, 7]]console.log(zigzagLevelOrder(buildTree([1, 2, 3, 4, null, null, 5])));         // [[1], [3, 2], [4, 5]]console.log(zigzagLevelOrder(buildTree([])));                                  // []
How it works

O(n) time, and no extra pass to reverse. Saving the size is what makes this possible.

Approach 3Depth-first, building rows from either end
The idea

Walk depth-first, left before right, and pass the depth along. On even depths push the value onto the row; on odd depths unshift it to the front.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function zigzagLevelOrder(root) {  const levels = [];  function walk(node, depth) {    if (node === null) return;    if (levels.length === depth) levels.push([]);    if (depth % 2 === 0) levels[depth].push(node.val);    else levels[depth].unshift(node.val);    walk(node.left, depth + 1);    walk(node.right, depth + 1);  }  walk(root, 0);  return levels;}console.log(zigzagLevelOrder(buildTree([3, 9, 20, null, null, 15, 7])));      // [[3], [20, 9], [15, 7]]console.log(zigzagLevelOrder(buildTree([1, 2, 3, 4, null, null, 5])));         // [[1], [3, 2], [4, 5]]console.log(zigzagLevelOrder(buildTree([])));                                  // []
How it works

Correct, but unshift moves the whole row each time, so a very wide row costs O(row²). It is fine for interviews. For speed, prefer the earlier two.

Which approach should you use?

Reverse at the end if you want it clear. Use the mirror write to avoid the extra pass. (LeetCode 103.)

Q4Minimum depth of binary treeEasy

Return the minimum depth of a binary tree: the number of nodes on the shortest path from the root down to a leaf.

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: 2
Explanation: The leaf 9 is the closest leaf. The path is 3, 9, which has two nodes.
Example 2
Input: root = [2, null, 3, null, 4, null, 5, null, 6]
Output: 5
Explanation: This is a chain. The only leaf is 6, at depth 5. The root is not a leaf, even though it has no left child.
Example 3
Input: root = []
Output: 0
Explanation: An empty tree has depth 0.
Stuck? Open one hint at a time
Hint 1
Be careful about what a leaf is: a node with no children at all.
Hint 2
Which walk reaches the nodes near the top first, so that you can stop early?
Show all 3 solutions with explanations
Approach 1Collect every leaf depth, take the smallest (brute force)
The idea

Walk the whole tree depth-first. Each time you reach a leaf, record its depth. Return the smallest one.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function minDepth(root) {  if (root === null) return 0;  let best = Infinity;  function walk(node, depth) {    if (node.left === null && node.right === null) best = Math.min(best, depth);    if (node.left) walk(node.left, depth + 1);    if (node.right) walk(node.right, depth + 1);  }  walk(root, 1);  return best;}console.log(minDepth(buildTree([3, 9, 20, null, null, 15, 7])));           // 2console.log(minDepth(buildTree([2, null, 3, null, 4, null, 5, null, 6]))); // 5console.log(minDepth(buildTree([])));                                      // 0
How it works

O(n) time, O(h) space. It always visits every node, even when a leaf is right below the root.

Approach 2Recursion that handles nodes with one child
The idea
  1. If the node is null, the answer is 0.
  2. If the left side is missing, the answer is 1 plus the right side. If the right side is missing, the answer is 1 plus the left side.
  3. Otherwise the answer is 1 plus the smaller of the two sides.
JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function minDepth(root) {  if (root === null) return 0;  if (root.left === null) return 1 + minDepth(root.right);  if (root.right === null) return 1 + minDepth(root.left);  return 1 + Math.min(minDepth(root.left), minDepth(root.right));}console.log(minDepth(buildTree([3, 9, 20, null, null, 15, 7])));           // 2console.log(minDepth(buildTree([2, null, 3, null, 4, null, 5, null, 6]))); // 5console.log(minDepth(buildTree([])));                                      // 0
How it works

O(n) time, O(h) space. The two special cases are the whole point: a missing child is not the end of a path.

Approach 3BFS that stops at the first leaf
The idea

Go row by row. The first leaf you meet is on the row nearest the top. So return the current depth at once.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function minDepth(root) {  if (root === null) return 0;  const queue = [root];  let head = 0;  let depth = 1;  while (head < queue.length) {    const size = queue.length - head;    for (let k = 0; k < size; k++) {      const node = queue[head++];      if (node.left === null && node.right === null) return depth;      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    depth++;  }  return depth;}console.log(minDepth(buildTree([3, 9, 20, null, null, 15, 7])));           // 2console.log(minDepth(buildTree([2, null, 3, null, 4, null, 5, null, 6]))); // 5console.log(minDepth(buildTree([])));                                      // 0
How it works

O(n) in the worst case, but it can finish after looking at only the rows down to the first leaf. It uses O(w) space.

Which approach should you use?

BFS is the natural fit and can stop early. The recursion is shorter if you remember the one-child case. (LeetCode 111.)

Q5Average of levels in binary treeEasy

Return the average value of the nodes on each level of a binary tree, as an array from the top level down.

Example 1
Input: root = [3, 9, 20, 15, 7]
Output: [3, 14.5, 11]
Explanation: Row 1: (9 + 20) / 2 = 14.5. Row 2: (15 + 7) / 2 = 11.
Example 2
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [3, 14.5, 11]
Explanation: The rows have the same values, but the tree has a different shape.
Stuck? Open one hint at a time
Hint 1
For each row, you need the sum and the number of nodes.
Hint 2
In BFS, the saved size is the number of nodes in the row.
Show all 2 solutions with explanations
Approach 1BFS with a running sum
The idea

For each row, add up the values while you process size nodes. Then push sum / size to the answer.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function averageOfLevels(root) {  if (root === null) return [];  const averages = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    let sum = 0;    for (let k = 0; k < size; k++) {      const node = queue[head++];      sum += node.val;      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    averages.push(sum / size);  }  return averages;}console.log(averageOfLevels(buildTree([3, 9, 20, 15, 7])));                 // [3, 14.5, 11]console.log(averageOfLevels(buildTree([3, 9, 20, null, null, 15, 7])));     // [3, 14.5, 11]
How it works

O(n) time, O(w) space. We do not keep the values, only their sum.

Approach 2DFS adding up sums and counts for each depth
The idea

Keep two arrays, with the depth as the index: one for the sum and one for the count. Walk depth-first and add each node to the entries of its depth. Divide at the end.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function averageOfLevels(root) {  const sums = [], counts = [];  function walk(node, depth) {    if (node === null) return;    if (depth === sums.length) { sums.push(0); counts.push(0); }    sums[depth] += node.val;    counts[depth]++;    walk(node.left, depth + 1);    walk(node.right, depth + 1);  }  walk(root, 0);  return sums.map((s, i) => s / counts[i]);}console.log(averageOfLevels(buildTree([3, 9, 20, 15, 7])));                 // [3, 14.5, 11]console.log(averageOfLevels(buildTree([3, 9, 20, null, null, 15, 7])));     // [3, 14.5, 11]
How it works

O(n) time. O(h) for the call stack, plus two arrays whose length equals the height.

Which approach should you use?

Use BFS, because the question is exactly about rows. (LeetCode 637.)

Q6Find largest value in each tree rowMedium

Return an array of the largest value in each row of a binary tree, from the top row down.

Example 1
Input: root = [1, 3, 2, 5, 3, null, 9]
Output: [1, 3, 9]
Explanation: Row 0: 1. Row 1: max(3, 2) = 3. Row 2: max(5, 3, 9) = 9.
Example 2
Input: root = [1, 2, 3]
Output: [1, 3]
Explanation: Row 1 is 2 and 3, so the largest is 3.
Example 3
Input: root = []
Output: []
Explanation: No rows.
Stuck? Open one hint at a time
Hint 1
Use the same loop as the averages question, but keep the largest value instead of the sum.
Hint 2
Start the largest value at -Infinity (smaller than any number), because values can be negative.
Show all 2 solutions with explanations
Approach 1BFS with a running maximum
The idea

For each row, start at -Infinity, update it with every value, and push the result.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function largestValues(root) {  if (root === null) return [];  const result = [];  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    let max = -Infinity;    for (let k = 0; k < size; k++) {      const node = queue[head++];      max = Math.max(max, node.val);      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }    result.push(max);  }  return result;}console.log(largestValues(buildTree([1, 3, 2, 5, 3, null, 9])));   // [1, 3, 9]console.log(largestValues(buildTree([1, 2, 3])));                 // [1, 3]console.log(largestValues(buildTree([-1, -5, -2])));              // [-1, -2]console.log(largestValues(buildTree([])));                        // []
How it works

O(n) time, O(w) space.

Approach 2DFS keeping the best value for each depth
The idea

Walk depth-first and pass the depth. If this is a new depth, start its entry with the value of the node. Otherwise keep the larger value.

JavaScript
class TreeNode {  constructor(val, left = null, right = null) {    this.val = val;    this.left = left;    this.right = right;  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function largestValues(root) {  const result = [];  function walk(node, depth) {    if (node === null) return;    if (depth === result.length) result.push(node.val);    else result[depth] = Math.max(result[depth], node.val);    walk(node.left, depth + 1);    walk(node.right, depth + 1);  }  walk(root, 0);  return result;}console.log(largestValues(buildTree([1, 3, 2, 5, 3, null, 9])));   // [1, 3, 9]console.log(largestValues(buildTree([1, 2, 3])));                 // [1, 3]console.log(largestValues(buildTree([-1, -5, -2])));              // [-1, -2]console.log(largestValues(buildTree([])));                        // []
How it works

O(n) time, O(h) for the call stack. We start each depth with the first value we meet, so we do not need -Infinity.

Which approach should you use?

BFS is the most natural to read. Depth-first uses less memory on wide trees. (LeetCode 515.)

Q7Populating next right pointers in each nodeMedium

You get a perfect binary tree. Each node has an extra link called next. Set every next to point to the node on its right in the same row, or to null if there is none. All next links start as null.

Example 1
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: next pointers join each row: 1 → null; 2 → 3 → null; 4 → 5 → 6 → 7 → null
Explanation: In each row, every next pointer leads to the neighbour on the right. The last node points to null.
Example 2
Input: root = []
Output: (nothing to connect)
Explanation: An empty tree.
Stuck? Open one hint at a time
Hint 1
The tree is perfect: every node that is not a leaf has two children, and all leaves are on the same row.
Hint 2
With a saved size, the next of a node is simply the node at the front of the queue, unless it is the last node in its row.
Hint 3
To avoid the queue: a row that is already linked by next pointers lets you walk across it and link the row below.
Show all 3 solutions with explanations
Approach 1BFS with a saved size
The idea

For each row, process size nodes. For every node except the last one in the row, set next to the node now at the front of the queue (the next node in the same row). The last node keeps null.

JavaScript
class Node {  constructor(val, left = null, right = null, next = null) {    this.val = val;    this.left = left;    this.right = right;    this.next = next;      // will point at the node to the right on the same level  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new Node(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new Node(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new Node(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Read the tree back row by row by following the next pointers (for printing).function rows(root) {  const out = [];  for (let start = root; start !== null; start = start.left) {    const row = [];    for (let node = start; node !== null; node = node.next) row.push(node.val);    out.push(row);  }  return out;}function connect(root) {  if (root === null) return null;  const queue = [root];  let head = 0;  while (head < queue.length) {    const size = queue.length - head;    for (let k = 0; k < size; k++) {      const node = queue[head++];      if (k < size - 1) node.next = queue[head];   // the next node in this row      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);    }  }  return root;}console.log(rows(connect(buildTree([1, 2, 3, 4, 5, 6, 7])))); // [[1], [2, 3], [4, 5, 6, 7]]console.log(rows(connect(buildTree([1]))));                  // [[1]]console.log(rows(connect(buildTree([]))));                   // []
How it works

O(n) time and O(w) space for the queue. It works for any binary tree, not only a perfect one.

Approach 2Walk the finished row to link the row below (O(1) space)
The idea
  1. Start at the leftmost node of a row. That row is already linked through next.
  2. For each node in that row, connect node.left.next = node.right. If the node has a neighbour, also connect node.right.next = node.next.left (this crosses the gap between two parents).
  3. Drop down to the next row by moving to the leftmost node's left child.
JavaScript
class Node {  constructor(val, left = null, right = null, next = null) {    this.val = val;    this.left = left;    this.right = right;    this.next = next;      // will point at the node to the right on the same level  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new Node(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new Node(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new Node(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Read the tree back row by row by following the next pointers (for printing).function rows(root) {  const out = [];  for (let start = root; start !== null; start = start.left) {    const row = [];    for (let node = start; node !== null; node = node.next) row.push(node.val);    out.push(row);  }  return out;}function connect(root) {  let leftmost = root;  while (leftmost !== null && leftmost.left !== null) {    for (let node = leftmost; node !== null; node = node.next) {      node.left.next = node.right;      if (node.next !== null) node.right.next = node.next.left;    }    leftmost = leftmost.left;  }  return root;}console.log(rows(connect(buildTree([1, 2, 3, 4, 5, 6, 7])))); // [[1], [2, 3], [4, 5, 6, 7]]console.log(rows(connect(buildTree([1]))));                  // [[1]]console.log(rows(connect(buildTree([]))));                   // []
How it works

O(n) time and O(1) extra space. The next links we are making work like the queue. It needs every node to have both children (a perfect tree), so that node.left and node.next.left always exist.

Approach 3Recursion
The idea

At each node that has children, connect its two children to each other. Then connect the right child to the left child of the neighbour of the node. After that, call the function on both children. The parent has already linked the neighbour of a node before we get there.

JavaScript
class Node {  constructor(val, left = null, right = null, next = null) {    this.val = val;    this.left = left;    this.right = right;    this.next = next;      // will point at the node to the right on the same level  }}function buildTree(arr) {  if (arr.length === 0 || arr[0] === null) return null;  const root = new Node(arr[0]);  const queue = [root];  let head = 0, i = 1;  while (head < queue.length && i < arr.length) {    const node = queue[head++];    if (i < arr.length && arr[i] !== null) { node.left = new Node(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new Node(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Read the tree back row by row by following the next pointers (for printing).function rows(root) {  const out = [];  for (let start = root; start !== null; start = start.left) {    const row = [];    for (let node = start; node !== null; node = node.next) row.push(node.val);    out.push(row);  }  return out;}function connect(root) {  if (root === null || root.left === null) return root;  root.left.next = root.right;  root.right.next = root.next !== null ? root.next.left : null;  connect(root.left);  connect(root.right);  return root;}console.log(rows(connect(buildTree([1, 2, 3, 4, 5, 6, 7])))); // [[1], [2, 3], [4, 5, 6, 7]]console.log(rows(connect(buildTree([1]))));                  // [[1]]console.log(rows(connect(buildTree([]))));                   // []
How it works

O(n) time, O(h) space for the call stack. We set the links of the children before the recursive calls. This makes sure root.next is already correct when we need it.

Which approach should you use?

Start with BFS (it also solves the version for any tree, LeetCode 117). The O(1)-space row walk is the follow-up the interviewer hopes you know. (LeetCode 116.)

Make it stick

Make it stick — close this page, then
  1. Explain why a queue (and not a stack) produces level order.
  2. Explain what size = queue.length - head saves, and why you must take it before the inner loop.
  3. Say what BFS uses its extra space for, and when that is worse than a depth-first walk.
  4. Explain why BFS can stop early for minimum depth, and why a node with one child is not a leaf.
  5. Write level order from memory, then change it to give the right side view.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

So far a walk only visits nodes. Lesson 43 goes back to depth-first search, but now each call returns a value up to its parent. The values are heights, whether a tree is balanced, the diameter (the longest path) and path sums. The idea is simple: answer a question by combining what the left side and the right side report back. This one idea solves most of the harder tree problems.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series