Binary Tree Right Side View

Difficulty: Medium

Imagine standing to the right of a binary tree and looking at it straight on - from that vantage point, you'd only be able to see the rightmost node at each level, since taller nodes on the right can block the ones behind them.

Given the root of a binary tree, return the values of the nodes visible from the right side, ordered from the top level down to the bottom.

Examples

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

Level 0 shows 1. Level 1 shows 3 (2 is hidden behind it). Level 2 shows 4 (5 is hidden behind it).

Input: root = [1,null,3]
Output: [1,3]

Every level here has only one node, so both are visible.

Input: root = []
Output: []

An empty tree has nothing to view.

Constraints

  • The number of nodes in the tree is in the range [0, 100].

  • -100 <= Node.val <= 100

Approach

The visible node at each level is just the rightmost node in that level. A level-order (BFS) traversal already groups nodes by level, so the last value processed in each level's group is the answer for that level.

Alternatively, a depth-first traversal that always explores the right child before the left child will reach the rightmost node of each depth first - so recording the first value seen at each new depth (and never overwriting it) gives the same result.

Solutions

Iterative BFS

Traverse level by level with a queue, just like a normal level-order traversal, but only keep the value of the last node processed in each level.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function rightSideView(root) {
  if (root === null) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (i === levelSize - 1) {
        result.push(node.val);
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return result;
}

Time: O(n) · Space: O(n) — the queue can hold up to a whole level of nodes

Recursive DFS (Right First)

Do a depth-first traversal that visits the right child before the left child at every node. The first time the traversal reaches a given depth, that node is the rightmost one visible at that level, so record it and never overwrite it.

function rightSideView(root) {
  const result = [];

  function dfs(node, depth) {
    if (node === null) return;

    if (depth === result.length) {
      result.push(node.val);
    }

    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }

  dfs(root, 0);
  return result;
}

Time: O(n) · Space: O(h) — recursion stack depth, plus O(h) for the result array