DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Binary Tree Right Side View

mediumTrees

Problem statement

Imagine standing to the right of a binary tree and looking at it. At each level you can see only the rightmost node. Given the root, return the values you can see, from the top level down.

The visible node on a level is not always a right child: if the right side of the tree is shorter, a node from the left side shows through on the deeper levels. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [10, 6, 15, 3, 8, null, null, null, null, 7]

Output: [10, 15, 8, 7]

Explanation: The right branch stops at 15, so on the last two levels you see 8 and then 7, which is a left child.

Example 2

Input: root = [2, null, 9]

Output: [2, 9]

Hints

Approach

Walk the tree depth-first, visiting the right child before the left. The first node you reach at any depth is then the rightmost node of that depth.

  1. dfs(node, depth): if node is empty, return.
  2. If depth == len(view), this is the first node seen at this depth, so append its value.
  3. Recurse into node.right, then node.left, with depth + 1.

The condition in step 2 works because depths are discovered in increasing order: the list grows by one each time a deeper level is reached for the first time. Only the answer and the recursion stack are stored.

ComplexityTime O(n)Space O(h) for the recursion, besides the output
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional["TreeNode"]) -> list[int]:
view = []
def dfs(node, depth: int) -> None:
if node is None:
return
if depth == len(view): # first node reached at this depth
view.append(node.val)
dfs(node.right, depth + 1) # right first
dfs(node.left, depth + 1)
dfs(root, 0)
return view

Follow-up questions

  • Return the left side view instead.
  • Return the view from below: for each horizontal position, the lowest node.

Frequently asked questions

It misses levels where the right side has run out. In the first example, 15 has no children, so walking only right pointers stops at [10, 15], while 8 and 7 are still visible from the side.

Yes. In the level loop, record only the value of the last node popped (when the loop counter hits the end of the level). That keeps BFS at O(w) space, which can beat the DFS version on a tall, thin tree.

Picking one representative per level of a hierarchy is common, for example the last host in each tier of a rollout or the most recent entry at each depth of a nested structure. The broader skill is carrying depth through a traversal.