LeetCode 199 · Trees

Binary Tree Right Side View, explained with a picture

What you see standing to the right of the tree.

MediumTrees
▶ Watch it step by step

The problem

Imagine standing on the right side of a binary tree. Return the values you can see, from top to bottom.

Input:  [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]

Picture it

Picture yourself standing to the right of the tree, looking left. On each row (level) you can only see the node nearest to you: the rightmost one, which hides the others behind it. A level-by-level walk tells us the last node in each row.

How to recognise it

  • The answer has one value per level: the node you would see from the right.
  • That is the last node of each level in left-to-right order, so the problem is level order traversal with a small change.
  • The rightmost node is not always on the right edge: if a level has nothing on the right, a left-side node shows through.
  • Up to 100 nodes, so any approach that visits each node once is plenty.

Start with brute force

For each depth d = 0, 1, 2, ..., search the tree right child first and stop at the first node found at depth d. Stop when a depth has no nodes.

def right_view_brute(root):
    view, d = [], 0
    while True:
        found = []
        def rightmost(node, depth):
            if not node or found:
                return
            if depth == d:
                found.append(node.val)
                return
            rightmost(node.right, depth + 1)
            rightmost(node.left, depth + 1)
        rightmost(root, 0)
        if not found:
            return view
        view.append(found[0])
        d += 1

Each depth starts again from the root, so the levels above are walked again every time: up to O(n · h) time, where h is the height. With at most 100 nodes that is at most about 10^4 steps, so it passes; the point is the cleaner one-pass method.

From brute force to the idea

  1. Find the waste. Each depth re-walks every level above it.
  2. Go level by level once. A breadth-first search (BFS: visit all nodes at one distance before any farther ones) with a deque processes the tree in rounds, one level per round, children pushed left before right.
  3. Read the view before the round. At the start of a round the queue holds exactly one level, in left-to-right order. Its last item, q[-1], is the rightmost node of that level. The shown code records it, then pops the round's len(q) nodes and pushes their children.
  4. Start safely. deque([root] if root else []) makes an empty tree give an empty queue, so the loop never runs.

This is the key idea: run level order BFS and keep the last node of every level.

A depth-first version also works: visit right before left, and record a node when its depth equals the number of values seen so far. The shown code needs from collections import deque.

The key idea

BFS by levels and keep the last value of each level. O(n).

Python solution

def right_side_view(root):
    view, q = [], deque([root] if root else [])
    while q:
        view.append(q[-1].val)          # last in the row is visible
        for _ in range(len(q)):
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return view

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (one search per depth)O(n · h): levels above are re-walked for every depthO(h): recursion stack
BFS, last of each level (shown code)O(n): each node enters and leaves the queue onceO(w): the queue holds about one level, w is the widest level

Edge cases

  • Empty tree: returns [].
  • Left-only branch: [1, 2] gives [1, 2]; the 2 is visible because nothing is to its right.
  • Deeper level reached only from the left ([1, 2, 3, 4]): gives [1, 3, 4]; node 4 is under 2, not under 3.
  • Every level full: the view is just the right edge.
  • No recursion: a deep chain is fine.

Common mistakes

  • Following only right children from the root, which misses deeper levels that exist only on the left.
  • Reading q[-1] after the inner loop instead of before it; by then the queue holds the next level.
  • Pushing the right child before the left, which makes q[-1] the leftmost node instead.
  • Forgetting the empty-tree case, so deque([None]) reaches None.val.
Your turn: largest value in each row

Return the largest value on each level (LeetCode 515). For [1, 3, 2, 5, 3, null, 9] the answer is [1, 3, 9]. Describe your approach, then write it if you like.

Compare with our answer

Same BFS in rounds. Instead of the last node of the round, take the maximum value over the nodes in the queue at the start of the round.

from collections import deque

def largest_values(root):
    out, q = [], deque([root] if root else [])
    while q:
        out.append(max(node.val for node in q))
        for _ in range(len(q)):
            node = q.popleft()
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return out

Time O(n): each node is read once by max and popped once. Space O(w). Values may be negative, so do not start a running maximum at 0.

A strong answer mentions: that the queue holds exactly one level when the round starts, taking a maximum instead of the last item, and negative values.

Check what stuck

1. You must list, for each floor of an org chart, the newest employee on that floor (children are stored oldest first). Which approach fits best?

2. Why can the shown code read the visible node as q[-1] before popping?

3. A learner walks only node.right from the root and records each value. Which tree still gets the right answer?

Score 60% or more and the lesson is marked complete.