Right View of Tree

The problem, simply

You get a binary tree. Stand far away on its right side and look at it. On each floor (level) you see only the node closest to you, the rightmost one. Give back those nodes from the top floor to the bottom.

The trap: the rightmost node on a deep floor can live in the left part of the tree, if the right part is shorter.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read the tree row by row with a waiting line (a queue). The last node taken out of each row is the rightmost one.

1. Put the root in the line.
2. Read the line's size; that many nodes form this row.
3. Take them out one by one, adding their children to the back. Write down only the last one (i == size - 1).
4. Repeat until the line is empty.

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        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();
            for (int i = 0; i < size; i++) {
                TreeNode node = line.poll();
                if (i == size - 1) out.add(node.val);   // last one in the row
                if (node.left != null) line.add(node.left);
                if (node.right != null) line.add(node.right);
            }
        }
        return out;
    }
}

How long it takes: O(n), each node once. Extra room: one full row in the line, O(w).

Way 2: the clever way

Walk the tree going right first, carrying the floor number. The answer list remembers which floors are taken: if it has exactly floor names, this is the first node we meet on this floor, and because we go right first, it is the rightmost one.

1. Visit a node with its floor number d.
2. If answer.size() == d, add the node.
3. Visit the right child with d + 1, then the left child with d + 1.

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        see(root, 0, out);
        return out;
    }

    private void see(TreeNode node, int floor, List<Integer> out) {
        if (node == null) return;
        if (out.size() == floor) out.add(node.val);   // first one we meet on this floor
        see(node.right, floor + 1, out);              // right first
        see(node.left, floor + 1, out);
    }
}

How long it takes: each node once, O(n). Extra room: the call stack, O(h).

Watch out for

• Writing the first node of each row in Way 1 gives the left view. You need the last one.
• If you use a maxLevel field instead of out.size(), reset it on each call.
• An empty tree returns an empty list in both ways.

What interviewers ask next

• Left view: go left first, or keep the first node of each row.
• Rightmost value on the deepest floor only: same walk, keep only the last name you add.
• Do it with O(1) extra room. Not with plain recursion, which uses the call stack. A Morris style walk can track depth, but it is rarely expected.
• Can you get both views in one pass? Yes: in the queue version, write the first and the last node of every row.

Remember this

Grown-up words: floors are levels, the waiting line is a queue for breadth first search, the right-first walk is a depth first search (a reversed preorder), and the pile of waiting helpers is the call stack.