Binary Tree Right Side View

MediumBreadth-first searchLeetCode 199 ↗World 3-8

0:00 / 0:00

List the nodes you'd see standing to the right of a binary tree. Walk it level by level and keep the last node on each level.

▼

The problem

LeetCode 199 (Medium). Given the root of a binary tree, imagine standing on its right side and return the values of the nodes you can see, ordered from top to bottom: the rightmost node of every level.

Examples (LeetCode's): [1,2,3,null,5,null,4] → [1,3,4], [1,null,3] → [1,3] and [] → [].

TRY IT ON LEETCODE ▶

The solution

def rightSideView(root):
    view = []
    level = [root] if root else []
    while level:
        view.append(level[-1].val)
        level = [kid for node in level
                 for kid in (node.left, node.right) if kid]
    return view

Transcript

Binary Tree Right Side View. Picture the sun setting to the right of a binary tree. On each level, its low light hits only the nearest node, the one you'd see from that side. Return those values, top to bottom.

In the first example, the light finds one, then three, then four. One with a right child three gives one, three. An empty tree gives an empty list.

The tempting shortcut: slide down the right children. Try one, two, three, four, where four hangs under two. The right path stops at three, but nothing on four's level blocks the light. The answer is one, three, four, so the shortcut misses four.

Instead, go level by level, breadth first. Keep each level's nodes in order, left to right. The last one is the node the sun hits. Then build the next level from their children, left before right.

In code, while the level has nodes, add its last value to the view, then replace the level with all their children, in order.

Try a bigger tree. Level one is just one. Level two is two, three, so three is lit. Level three is four, five, six: six is lit. Seven sits alone on the far left, but it's last on level four, so it's lit. The view is one, three, six, seven.

Each node joins a level once, so it's order n time. We hold one level at a time, so the space is order of the tree's width.

Level by level, keep the last. That's Binary Tree Right Side View.