AlgoMaster Logo

Binary Tree Right Side View

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We are looking at a binary tree from the right side. For each level of the tree, we want the rightmost visible node. That does not always mean "the right child." If a level has nodes only in the left subtree, the leftmost node at that level is still the one you would see from the right, because nothing blocks it.

So the real question is: for every depth level in the tree, what is the last node when we scan left to right? This reframes the problem from a spatial "standing on the right" visualization to a concrete algorithmic task: find the last node at each level.

This connects directly to level-order traversal. If we process each level left to right, the last node we process at each level is our answer. But we can also solve this with DFS by visiting the right subtree first.

Key Constraints:

  • Number of nodes in range [0, 100]: The input is small enough that any linear traversal finishes instantly, so the choice between approaches comes down to space usage and code structure, not speed.
  • -100 <= Node.val <= 100: Node values can be negative. This does not affect the traversal logic.
  • The tree can be empty (0 nodes), so we need to handle the null root case.

Approach 1: BFS (Level Order Traversal)

Intuition

Process the tree level by level, scanning each level from left to right. The last node processed at each level is the one visible from the right side, and BFS with a queue produces this order directly.

At each level, we record the queue size before processing, dequeue exactly that many nodes, and add the value of the last one to the result. Children enqueued during a level form the next level, so the size snapshot cleanly separates one level from the next.

Algorithm

  1. If the root is null, return an empty list.
  2. Create a queue and add the root.
  3. While the queue is not empty:
    • Record the current queue size as levelSize.
    • Process exactly levelSize nodes from the queue.
    • For each node, enqueue its left and right children (if they exist).
    • The last node processed in this level is the right side view node. Add its value to the result.
  4. Return the result list.

Example Walkthrough

1Start BFS: queue = [1]
1queue2534
1/7

Code

BFS is already O(n) in time, which is optimal. But the queue holds an entire level at once, up to roughly n/2 nodes for a wide tree. The next approach replaces that level-wide queue with a recursion stack whose size is proportional to the tree's height, not its width.

Approach 2: DFS (Right-First Traversal)

Intuition

A depth-first traversal that visits the right child before the left child reaches the rightmost node of each level before any other node at that depth. So instead of scanning a whole level and keeping the last node, we record the first node encountered at each new depth.

Detecting a "new" depth requires no extra data structure. Compare the current depth against the size of the result list: if depth == result.size(), no node at this depth has been recorded yet, so the current node is the rightmost one at this level.

Algorithm

  1. If the root is null, return an empty list.
  2. Create an empty result list.
  3. Define a recursive function dfs(node, depth):
    • If node is null, return.
    • If depth equals the size of result, this is the first node we have seen at this depth. Add node.val to the result.
    • Recurse on the right child with depth + 1 (right child first).
    • Recurse on the left child with depth + 1.
  4. Call dfs(root, 0) and return the result.

Example Walkthrough

1dfs(1, depth=0): new depth! Add 1, result = [1]
1add to result2534
1/6

Code