Reverse Level Order traversal

The problem, simply

You get a binary tree. Read it row by row (level by level), but start with the bottom row and finish with the root. Inside each row, still read from left to right.

The classic version gives back one flat list of values. Another common version gives back a list of rows.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the height first. Then for each row number from the bottom up, walk the whole tree from the root and collect only the nodes on that row.

1. Compute the height h.
2. For row = h down to 1, walk the tree and add every node whose row number is row, left side first.

import java.util.*;

class Solution {
    public List<Integer> reverseLevelOrder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        for (int row = height(root); row >= 1; row--) {
            collect(root, row, out);          // walk from the top every time
        }
        return out;
    }

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

    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. For a stick shaped tree that is n rows times n steps, O(n^2). Extra room: the call stack, O(h).

Way 2: the clever way

Read the tree top down with a waiting line (a queue), but put every node on a plate pile (a stack) instead of writing it. At the end, take the plates off the top.

To make each row come out left to right after the pile turns it around, add the right child to the line before the left child.

1. Put the root in the line.
2. Take the front node, push it on the pile.
3. Add its right child, then its left child, to the back of the line.
4. When the line is empty, pop the pile into the answer.

import java.util.*;

class Solution {
    public List<Integer> reverseLevelOrder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Queue<TreeNode> line = new ArrayDeque<>();
        Deque<Integer> pile = new ArrayDeque<>();
        line.add(root);
        while (!line.isEmpty()) {
            TreeNode node = line.poll();
            pile.push(node.val);                              // plate on the pile
            if (node.right != null) line.add(node.right);     // right first
            if (node.left != null) line.add(node.left);
        }
        while (!pile.isEmpty()) out.add(pile.pop());          // last plate first
        return out;
    }
}

How long it takes: each node goes through the line once and the pile once, O(n). Extra room: the pile holds every value, O(n).

If you need a list of rows, do a normal level order (left child first), collect each row as a list, and add each row at the front of a linked list, or reverse the list of rows at the end. Rows keep their left to right order because you only reverse the order of the rows, not the rows themselves.

Watch out for

• In the list of rows version, do not push right first. There you reverse whole rows, not single values.
• Collections.reverse on the final flat list of a normal level order gives the wrong answer for the same reason as the trap.
• An empty tree: return before touching the queue.

What interviewers ask next

• Return the rows bottom up as lists. Normal level order, then Collections.reverse(rows), or rows.add(0, row) on a LinkedList.
• Can you avoid the stack? Yes for the rows version: compute the height, make an array of that many empty rows, and fill row h - 1 - depth during the walk.
• Print the bottom row only. That is the last row of a level order.
• Reverse level order with each row right to left. Plain level order, left child first, with a stack, then pop.

Remember this

Grown-up words: rows are levels, the waiting line is a queue for breadth first search, the plate pile is a stack (last in, first out), and the rows version is LeetCode's "level order traversal II".