Binary Tree Right Side View

Binary Tree Right Side View

What is this problem about?

Imagine you are standing on the right side of a binary tree. Which nodes would you be able to see? The Binary Tree Right Side View interview question asks you to return the values of these nodes in order from top to bottom. Essentially, for every level of the tree, you want to find the rightmost node.

Why is this asked in interviews?

This is a classic "level-based" problem asked by companies like Google, Meta, and Amazon. It tests your ability to modify a standard traversal to extract specific information. It can be solved using either BFS or DFS, making it a great way to show off your flexibility. It also tests your understanding of tree depth and level tracking.

Algorithmic pattern used

There are two common ways to solve this:

1. BFS (Breadth-First Search): Perform a level-order traversal. For each level, only add the last node processed to your result list.
2. DFS (Depth-First Search): Use a modified preorder traversal (Root -> Right -> Left). Keep track of the current depth. If the current depth is equal to the number of nodes in your result list, it means this is the first time you've reached this level from the right side, so add the node.

Example explanation

Consider this tree: 1 <--- (1) /
2 3 <--- (3) \
5 4 <--- (4)

1. At Level 0, the rightmost node is 1.
2. At Level 1, the rightmost node is 3. (2 is hidden behind 3).
3. At Level 2, the rightmost node is 4. (5 is hidden if 4 is there, but if 4 wasn't there, we would see 5). Result: [1, 3, 4].

Common mistakes candidates make

A common mistake is thinking you only need to follow the "right" pointers from the root. This is wrong because a node on the far left might be the only node at a very deep level, making it visible from the right side. Another mistake is using BFS but failing to identify which node is the "last" one in each level.

Interview preparation tip

Try solving this with both BFS and DFS. The BFS approach is more intuitive for "level" problems, but the DFS approach is often more elegant and uses less extra space (aside from the recursion stack).