Binary Tree Right Side View

The problem

root is the top node of a binary tree, or null when the tree is empty. Each node has a number val and up to two children, left and right; a missing child is null. The root is on level 0, its children on level 1, and so on. Imagine looking at the tree from its right side. On each level you can see only the rightmost node, the last one when the level is listed from left to right; it hides the others. Return the values of the visible nodes, from the top level down. An empty tree returns an empty list.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null): number[]

Input
root = {"val":1,"left":{"val":2,"left":null,"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":{"val":4,"left":null,"right":null}}}

Output
[1,3,4]

Input
root = {"val":1,"left":null,"right":{"val":3,"left":null,"right":null}}

Output
[1,3]

Constraints

Trees use {val, left, right}; the input may be empty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The answer has exactly one value for each level of the tree, so its length is the number of levels. A visible node is not always a right child: when a level's only node is a left child, that is the node you see. An empty tree gives an empty list.

2. Hint 2: Ask a smaller question

   In example 1, write the nodes of each level from left to right: 1, then 2 and 3, then 5 and 4. Which node of each level is in the answer? Now list each level from right to left instead. Where in its level does each answer sit?

3. Hint 3: Name the pattern

   The answer is one node per level, so each node must know its level, and only its parent can tell it. A function handles a node, then calls itself on each child with the level plus one. Carrying information down like this is preorder tree recursion. Going right first, the first node reached on a level is its rightmost. Read the lesson on preorder tree recursion.

4. Hint 4: State the invariant

   The answer list holds one value for each level reached so far, so its length tells you which levels are taken. A node whose level number equals that length is the first node reached on its level, and because right goes first, it is the rightmost.

5. Hint 5: Sketch the pseudocode

   Keep an empty answer list. visit(node, level): if the node is missing, return. If level equals the length of the answer list, append the node's value. Then visit(right child, level + 1), then visit(left child, level + 1). Call visit(root, 0) and return the list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Visit right children first. The first value reached at each depth is the visible node.

The slow way

Collect every level from left to right with a queue, one level at a time, and keep the last value of each level. It is correct, but it holds whole levels in memory, which can be about half of the tree at once, and then uses a single value from each.

The insight

You need one node per level: the rightmost. If you always walk into the right child before the left one, then on every level the rightmost node is the first one you reach. So you only have to notice when you arrive on a level for the first time.

Step by step

1. Keep one answer value per level, top level first. The list fills in order, level 0 first. So its length always says how many levels already have their visible node.
2. A missing node has nothing to show. A missing child ends this branch of the walk. An empty tree is the same case: the walk ends at once and the list stays empty.
3. The first node reached on a level is the visible one: record it. The list's length equals the node's level only if no node of that level was recorded before. Since right sides are walked first, this node is the rightmost one.
4. Visit the right child before the left, one level further down. Everything under the right child is walked before anything under the left child. So of two nodes on one level, the one further right is always reached first.
5. Start at the root, on level 0. The root is the only node on level 0 and the list is empty, so the root is recorded first. The numbering matches the list's positions, which also start at 0.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. Keep one answer value per level, top level first
  const out = [];
  function visit(n, d) {
    // 2. A missing node has nothing to show
    if (!n) return;
    // 3. The first node reached on a level is the visible one: record it
    if (d === out.length) out.push(n.val);
    // 4. Visit the right child before the left, one level further down
    visit(n.right, d + 1);
    visit(n.left, d + 1);
  }
  // 5. Start at the root, on level 0
  visit(root, 0);
  return out;
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null): number[] {
  // 1. Keep one answer value per level, top level first
  const out: number[] = [];
  function visit(n: TreeNode | null, d: number): void {
    // 2. A missing node has nothing to show
    if (!n) return;
    // 3. The first node reached on a level is the visible one: record it
    if (d === out.length) out.push(n.val);
    // 4. Visit the right child before the left, one level further down
    visit(n.right, d + 1);
    visit(n.left, d + 1);
  }
  // 5. Start at the root, on level 0
  visit(root, 0);
  return out;
}

def solve(root):
    # 1. Keep one answer value per level, top level first
    out = []

    def visit(node, depth):
        # 2. A missing node has nothing to show
        if node is None:
            return
        # 3. The first node reached on a level is the visible one: record it
        if depth == len(out):
            out.append(node.val)
        # 4. Visit the right child before the left, one level further down
        visit(node.right, depth + 1)
        visit(node.left, depth + 1)

    # 5. Start at the root, on level 0
    visit(root, 0)
    return out

Example 1, traced

Input
root = {"val":1,"left":{"val":2,"left":null,"right":{"val":5,"left":null,"right":null}},"right":{"val":3,"left":null,"right":{"val":4,"left":null,"right":null}}}

Output
[1,3,4]

Why it works

Right children are walked before left ones, so of two nodes on the same level the one further right is reached first. The first node reached on a level is therefore its rightmost. A level is reached only after the level above it, so the list gets exactly one value per level, in order from the top.

Time and space

Time O(n), extra space O(h). Every node is visited once and does a fixed amount of work: O(n) time. The unfinished calls lie along one path down the tree, at most about h of them, where h is the tree's height, its number of levels. The answer holds h values too: O(h) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not follow only the right children. When the right side ends early, deeper levels still show a node from the left side: a root 1 whose only child is a left child 2 must give [1, 2], not [1].
• Visit the right child before the left one. With left first, the first node reached on each level is the leftmost, and example 1 returns [1, 2, 5], the view from the left.
• Start the root on level 0, to match an empty list. With the root on level 1, the level never equals the list's length, nothing is recorded, and every tree returns an empty list.

Pattern

Preorder tree recursion. Builds on Maximum Depth of Binary Tree and Binary Tree Level Order Traversal.

Keep going