Binary Tree Right Side View

MediumTreesTreeDFSBFSBinary Tree

Problem

Given a binary tree, imagine standing to its right and looking at it edge-on. Return the values of the nodes visible from that side, ordered from the top level down. At each depth, only the rightmost node is visible.

Example. For a tree with root 1, left child 2, right child 3, where 2 has a right child 5 and 3 has a right child 4, the right side view is [1, 3, 4]; 5 is hidden behind 4 at the same depth.

Key idea

A tempting first move is to record every node with its depth, then group those records afterward and pick the last value per group. That works, but it is a level-order traversal with extra bookkeeping tacked on.

It is cleaner to select while traversing. Process the tree level by level with a queue: whichever node is visited last at a given depth is the one visible from the right. A depth-first walk that always recurses right before left reaches each depth's rightmost node first, so recording a depth's value only on first arrival gives the same list without a queue.

Solution

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

function rightSideView(root: TreeNode | null): number[] {
  const view: number[] = [];

  function dfs(node: TreeNode | null, depth: number): void {
    if (node === null) {
      return;
    }
    if (depth === view.length) {
      // First arrival at this depth is the rightmost node, since right is visited before left.
      view.push(node.val);
    }
    // Recurse right first so each depth's rightmost node is recorded before any left-side node.
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }

  dfs(root, 0);
  return view;
}

Complexity

  • Time: O(n). Every node is visited exactly once.
  • Space: O(n). The queue (or recursion stack) can hold an entire level, which is proportional to n for a wide tree.

Watch out for

  • The rightmost node at a depth is not always reached by following right children; it can be a left child if the right subtree doesn't extend that far.
  • With DFS, recurse right before left and only record a depth on first arrival, or a later left-side node overwrites the correct value.
  • A level with a single node still contributes to the view.

Pattern

This is level-order traversal with a "keep the last node per level" twist. The same per-depth processing shows up in level order traversal, per-level averages, and zigzag traversal: any problem concerned with structure at each depth rather than the tree as a whole.

Related questions