Left View of a tree

The problem, simply

You get a binary tree. Imagine you stand far away on its left side and look at it. On every floor (level) you can only see the first node, the one closest to you. Everyone else on that floor hides behind it.

Give back those visible nodes, from the top floor to the bottom floor.

The visible node on a floor is not always a left child. If the left side of the tree is short, a node from the right side can peek out on a lower floor.

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), like level order. The first node you take out of each row is the one seen from the left.

1. Put the root in the line.
2. Read the line's size. That many nodes make up this row.
3. Take them out one by one. Write down only the first one (i == 0). Add every node's children to the back.
4. Repeat until the line is empty.

import java.util.*;

class Solution {
    public List<Integer> leftView(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();                 // nodes in this row
            for (int i = 0; i < size; i++) {
                TreeNode node = line.poll();
                if (i == 0) out.add(node.val);      // first 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: every node joins and leaves the line once, O(n). Extra room: the line holds one whole row, O(w) where w is the widest row. That can be about n / 2.

Way 2: the clever way

Walk the tree going left first, and carry the floor number. Use the answer list itself as the memory of which floors are already taken: if the list has exactly floor names, nobody from this floor has been written yet.

1. Visit a node with its floor number d.
2. If answer.size() == d, this is the first node we meet on floor d. Add it.
3. Visit the left child with d + 1, then the right child with d + 1.

Because left is always visited before right, the first node you meet on each floor is the leftmost one.

import java.util.*;

class Solution {
    public List<Integer> leftView(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 on this floor
        see(node.left, floor + 1, out);               // left first
        see(node.right, floor + 1, out);
    }
}

How long it takes: each node once, O(n). Extra room: only the pile of waiting helpers, as tall as the tree, O(h). For a bushy tree that is much smaller than the widest row.

Watch out for

• Visiting right before left gives the right view, not the left view.
• Using a shared maxLevel field is fine, but reset it before every call, or a second call returns nothing. Using out.size() avoids that bug.
• An empty tree. Both ways return an empty list.

What interviewers ask next

• Right view: visit the right child first, or take the last node of each row in Way 1.
• Bottom view and top view: those look from below and above, so you need columns (left is -1, right is +1), not floors.
• Print the boundary of the tree: left edge, then all leaves, then the right edge upwards. The left view is a different thing from the left edge, so be careful.
• Can it be done with no recursion and no queue? You can simulate Way 2 with your own stack of (node, floor) pairs, pushing right before left.

Remember this

Grown-up words: floors are levels or depths, the waiting line is a queue for breadth first search, going left first with a floor number is a preorder depth first search, and the pile of waiting helpers is the call stack.