Level order traversal

The problem, simply

A binary tree is a family tree where every person has at most two children: a left child and a right child. The person at the very top is the root.

Read the names row by row. First the top row, then the row under it from left to right, then the next row, and so on. Give back each row as its own list.

A story to remember it

Picture it

Examples

Way 1: the simple way

First find how many rows there are. Then for each row number, start at the top again and walk down, writing down only the nodes that sit on that row.

1. Count the height h of the tree.
2. For row = 0 to h - 1, walk the whole tree with a depth counter and collect the nodes whose depth equals row.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        int h = height(root);
        for (int row = 0; row < h; row++) {
            List<Integer> names = new ArrayList<>();
            collect(root, 0, row, names);   // walk from the top every time
            out.add(names);
        }
        return out;
    }

    private void collect(TreeNode node, int depth, int row, List<Integer> names) {
        if (node == null) return;
        if (depth == row) { names.add(node.val); return; }
        collect(node.left, depth + 1, row, names);
        collect(node.right, depth + 1, row, names);
    }

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

How long it takes: for each of the h rows we may walk most of the tree again. In a tree shaped like a long stick, h is n, so this is O(n^2). Extra room: the walk goes as deep as the tree, O(h).

Way 2: the clever way

Use a waiting line, a queue. People join at the back and leave from the front.

1. Put the root in the line.
2. While the line is not empty, count how many people are in it right now. That count is the size of the current row.
3. Take exactly that many people from the front. Write each name down, and put their left and right children at the back of the line.
4. The names you wrote form one row. Repeat.

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        while (!line.isEmpty()) {
            int size = line.size();            // how many nodes are in this row
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = line.poll();   // leave from the front
                row.add(node.val);
                if (node.left != null) line.add(node.left);    // join at the back
                if (node.right != null) line.add(node.right);
            }
            out.add(row);
        }
        return out;
    }
}

How long it takes: every node joins the line once and leaves once, O(n). Extra room: the line holds at most one full row, which is the widest row w of the tree, O(w). In the worst case that is about n / 2.

Watch out for

• A null root. Return an empty list first.
• Adding null children to the queue. Check before you add, or skip null when you poll.
• Using a stack instead of a queue. A stack takes the newest person first and you get a deep dive, not rows.

What interviewers ask next

• Zigzag order: flip every second row before adding it, or add to the front of the row list on odd rows.
• Right side view: keep only the last name of each row.
• Bottom up order: build the rows the same way, then reverse the list of rows.
• Largest value in each row, or the average of each row: same loop, different thing written down.
• Can you do it with depth first search? Yes. Carry the depth, and add the value to out.get(depth). It visits nodes in a different order but builds the same rows.

Remember this

Grown-up words: the photo steps are levels, reading row by row is breadth first search, the waiting line is a queue, and the widest row is the maximum width of the tree.