How do you solve Binary Tree Right Side View?

Use a queue initialized with the root node. For each level, iterate over all nodes currently in the queue, updating a variable to track the last node processed. Enqueue the children of each node for the next level. After processing the level, append the last node's value to the result list. Continue until the queue is empty. This guarantees an O(n) time complexity and O(n) space complexity.

Binary Tree Right Side View

Q: What is the time complexity of Binary Tree Right Side View?

O(n). Each node is enqueued and dequeued exactly once during the BFS traversal, resulting in linear time proportional to the number of nodes.

Q: What pattern does Binary Tree Right Side View use?

The Pattern: BFS (Level-Order Traversal for Layered State Exploration) The Heuristic: When a problem requires information about nodes at each depth or layer, use BFS to process nodes level by level, enabling direct access to the first or last node at each level without complex state tracking.

Medium BFS

Problem

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

The number of nodes in the tree is in the range [0, 100]
−100 ≤ Node.val ≤ 100

Example

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

Output: [1,3,4]

The tree structure is: 1 / \ 2 3 \ \ 5 4 A brute-force approach would be to traverse the tree and record all nodes at each level, then pick the rightmost node. The algorithm uses a breadth-first search (BFS) to traverse level by level. At each level, it processes all nodes, updating the rightmost node seen. For the example, at level 0, node 1 is the only node and thus the rightmost. At level 1, nodes 2 and 3 are processed; 3 is the rightmost. At level 2, nodes 5 and 4 are processed; 4 is the rightmost. Collecting these rightmost nodes yields [1,3,4].

Approach

Straightforward Solution

A naive approach would be to perform a DFS and track the rightmost node at each depth, but this requires careful state management and can be less intuitive.

Core Observation

The right side view of a binary tree corresponds to the rightmost node at each depth level when traversed level by level.

Path to Optimal

Preview

Recognizing that BFS naturally processes nodes level by level, the algorithm uses a queue to traverse the tree breadth-first. At each level, the last node processed is the rightmost node visible from that level…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a queue initialized with the root node. For each level, iterate over all nodes currently in the queue, updating a variable to track the last node processed…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is enqueued and dequeued exactly once during the BFS traversal, resulting in linear time proportional to the number of nodes.

Space

O(n)

The queue can hold up to the maximum number of nodes at any level, which in the worst case is proportional to n/2 (for a balanced tree), resulting in O(n) auxiliary space.

Pattern Spotlight

BFS (Level-Order Traversal for Layered State Exploration)

When a problem requires information about nodes at each depth or layer, use BFS to process nodes level by level, enabling direct access to the first or last node at each level without complex state tracking.

Solution

Python

1import collections
2
3class Solution:
  def rightSideView(self, root: TreeNode) -> list[int]:
      res = []
      if not root:
          return res
8
      q = collections.deque([root])
10
      while q:
          right_side = None
          q_len = len(q)
14
          for i in range(q_len):
              node = q.popleft()
              if node:
                  right_side = node
                  q.append(node.left)
                  q.append(node.right)
          
          if right_side:
              res.append(right_side.val)
      
      return res

Step-by-Step Solution

Initialize Result List Before BFS Traversal

5	`res = []`

Objective

To create the output list that will store the visible rightmost node value from each level.

Key Insight

The BFS loop determines one visible node per level, but those values need a stable container from the start. Initializing the result list before any queue logic makes the output flow explicit and also supports the empty-tree case cleanly.

Interview Quick-Check

Core Logic

Create the result list before traversal so each completed level can append one visible value.

State & Boundaries

The result container must exist even when the tree is empty, because the empty-tree case returns it directly.

Return Empty List for Empty Tree

To handle the edge case where the input tree is empty by returning an empty result immediately.

Traverse Tree Level-by-Level Using a Queue

To perform a breadth-first search that processes nodes level by level, tracking the rightmost node at each level.

Return the Collected Right Side View

To return the list of rightmost node values collected from each level after BFS completes.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 18 Critical

right_side = node

Update the rightmost node to the current node.

This assignment is critical because it captures the rightmost node at the current level; updating it for every valid node ensures the last one processed is the visible node from the right side.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does the BFS approach guarantee that the last node processed at each level is the rightmost visible node?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Binary Tree Right Side View from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Binary Tree Right Side View drill

or drill a free problem

1	`import collections`
2
3	`class Solution:`
4	`def rightSideView(self, root: TreeNode) -> list[int]:`
5	`res = []`
6	`if not root:`
7	`return res`
8
9	`q = collections.deque([root])`
10
11	`while q:`
12	`right_side = None`
13	`q_len = len(q)`
14
15	`for i in range(q_len):`
16	`node = q.popleft()`
17	`if node:`
18	`right_side = node`
19	`q.append(node.left)`
20	`q.append(node.right)`
21
22	`if right_side:`
23	`res.append(right_side.val)`
24
25	`return res`