Problem 16.8 · Binary TreesMedium

Binary Tree Right Side View

What it teaches: Per-level answers from BFS: the last node of each level is what you see from the right.

Practise it on judges as “Binary Tree Right Side View”.

The problem

Imagine standing to the right of the tree. Return the values you can see from top to bottom.

Example 1

Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]

Example 2

Input: root = [1, 2, 3, 4]
Output: [1, 3, 4]

4 is visible because nothing on the right is at its depth.

Constraints

0 ≤ nodes ≤ 100

Pattern clues in the wording

→ One value per level

These clues point to Tree BFS (Level Order): Process the tree level by level with a queue, handling exactly one level per loop.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	root = [1,2,3,null,5,null,4]	[1,3,4]
2	root = [1,2,3,4]	[1,3,4]
3	root = []	[]

From slow to fast

Approaches

1. BFS, last of each level · O(n)2. DFS right-first · O(n)

BFS, last of each level

Time O(n) Space O(width)

Level-order traversal; when polling the last node of a level (size reaches 1), record it.

Approach 1

import java.util.*;

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            for (int size = q.size(); size > 0; size--) {
                TreeNode n = q.poll();
                if (size == 1) out.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
        }
        return out;
    }
}

Verdict: Clear.

DFS right-first

Time O(n) Space O(h)

Visit right before left, passing the depth. The first node seen at each new depth is visible.

Approach 2

import java.util.*;

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

    private void dfs(TreeNode n, int depth, List<Integer> out) {
        if (n == null) return;
        if (depth == out.size()) out.add(n.val);
        dfs(n.right, depth + 1, out);
        dfs(n.left, depth + 1, out);
    }
}

Verdict: Elegant alternative.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty tree
Left subtree deeper than the right

Mistakes people make

Only following right pointers (misses deeper left nodes).

Interview

Follow-up questions

Left side view?

Command Palette