173. Right Side View

Why this mechanism works

Keep ordinary left-to-right BFS. The final node removed from each captured layer is that layer's rightmost existing node. This avoids guessing visibility from whether a node is a right child; visibility is a property of an entire depth.

State and boundaries

The queue begins each layer in left-to-right order. i identifies a node's position inside the captured width.

Protocol

1. Enqueue the root if present.
2. Capture layer width.
3. Process that many nodes left to right.
4. Record the value at i==width-1.
5. Enqueue children for the next layer.

Visualization

    1
   / \
  2   3
   \
    5
right view [1,3,5]

Python implementation

from collections import deque
from structures import build_tree

def right_side_view(root):
    if root is None:
        return []
    queue, output = deque([root]), []
    while queue:
        width = len(queue)
        for i in range(width):
            node = queue.popleft()
            if i == width - 1:
                output.append(node.val)
            for child in (node.left, node.right):
                if child is not None:
                    queue.append(child)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 right_side_view: if root is None:
root=N1(val=1,left=N2,right=N3)

L7 right_side_view: queue, output = deque([root]), []
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]

L9 right_side_view: width = len(queue)
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]; width=1

L10 right_side_view: for i in range(width):
root=N1(val=1,left=N2,right=N3); queue=deque([N1(val=1,left=N2,right=N3)]); output=[]; width=1; i=0

L11 right_side_view: node = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[]; width=1; i=0; node=N1(val=1,left=N2,right=N3)

L13 right_side_view: output.append(node.val)
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[1]; width=1; i=0; node=N1(val=1,left=N2,right=N3)

L14 right_side_view: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[1]; width=1; i=0; node=N1(val=1,left=N2,right=N3); child=N2(val=2,left=None,right=N4)

L16 right_side_view: queue.append(child)
root=N1(val=1,left=N2,right=N3); queue=deque([N2(val=2,left=None,right=N4)]); output=[1]; width=1; i=0; node=N1(val=1,left=N2,right=N3); child=N2(val=2,left=None,right=N4)

... 11 intermediate state changes omitted ...

L9 right_side_view: width = len(queue)
root=N1(val=1,left=N2,right=N3); queue=deque([N4(val=5,left=None,right=None)]); output=[1, 3]; width=1; i=1; node=N3(val=3,left=None,right=None); child=None

L10 right_side_view: for i in range(width):
root=N1(val=1,left=N2,right=N3); queue=deque([N4(val=5,left=None,right=None)]); output=[1, 3]; width=1; i=0; node=N3(val=3,left=None,right=None); child=None

L11 right_side_view: node = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[1, 3]; width=1; i=0; node=N4(val=5,left=None,right=None); child=None

L13 right_side_view: output.append(node.val)
root=N1(val=1,left=N2,right=N3); queue=deque([]); output=[1, 3, 5]; width=1; i=0; node=N4(val=5,left=None,right=None); child=None

L5 right_side_view: if root is None:
root=None

Why the solution is correct

The level-order invariant places each depth's rightmost node last. Recording exactly that last value therefore selects one correct visible node per depth. Left-before-right child insertion preserves the invariant for the next layer.

Time and space

O(n) time, O(w) queue space and O(h) output values.

Common mistakes

Following only right child pointers misses deeper visible nodes in left subtrees. Recording the last value in the entire traversal loses layer boundaries.

Reasoning card

Transfer exercise

Use right-first DFS and record the first node reached at each previously unseen depth.