Binary Tree Right Side View.

Problem. Imagine standing to the right of a binary tree. Return the values of the nodes you can see, ordered top to bottom — i.e., the rightmost node at each level.

The idea

"The node you see from the right" is just the last node on each level in left-to-right order. So this is the level-order template again: do BFS, and from each level grab the final element. The DFS variant flips it — visit right before left and record the first node encountered at each new depth.

      1          <- see 1
     / \
    2   3        <- see 3
     \   \
      5   4      <- see 4

right side view: [1, 3, 4]

BFS — O(n) time, O(n) space

Snapshot the level size; the node at index levelSize - 1 is the rightmost.

List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode n = q.poll();
            if (i == levelSize - 1) result.add(n.val);  // last node on this level
            if (n.left  != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
    }
    return result;
}

DFS — right-first, O(n) time, O(h) space

Recurse right child first. The first time the recursion reaches a given depth, that node is the rightmost at that depth — record it.

List<Integer> rightSideViewDFS(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, 0, result);
    return result;
}
private void dfs(TreeNode n, int depth, List<Integer> result) {
    if (n == null) return;
    if (depth == result.size()) result.add(n.val);  // first (= rightmost) at this depth
    dfs(n.right, depth + 1, result);                // right BEFORE left
    dfs(n.left,  depth + 1, result);
}

Both visit every node once — O(n) time. BFS uses O(w) queue space; DFS uses O(h) stack space.