Binary Tree Right Side View

Question

Given the root of a binary tree, return the values visible from the right side, ordered from top to bottom. Tests BFS/DFS fluency, a core skill Meta evaluates.

Codemia · Accepted Answer

The problem requires us to identify the nodes that are visible when looking at the binary tree from the right side. This suggests that we should consider how depth and breadth of the tree interact with visibility. The **BFS (Breadth-First Search)** approach is optimal here because it allows us to explore each level of the tree systematically. By keeping track of the rightmost node at each level, we can easily compile the list of visible nodes as we traverse the tree level by level.

1. Initialize a queue to facilitate the BFS traversal and add the root node to it.
2. Create a list to store the right side view of the binary tree.
3. While the queue is not empty, we will loop through each level of the tree:
   - Get the number of nodes at the current level.
   - For each node, pop it from the queue:
     - If it’s the last node in the level, append its value to the right side view list.
     - Add the right child to the queue first, then the left child (to ensure we see the rightmost node first).
4. Continue this until the queue is empty and return the right side view list.

**Example:** For the binary tree:
```
    1
   / \
  2   3
   \
    5
     \
      4
```
The right side view is [1, 3, 4] because:
- From the root (1), we see node 3 (the right child).
- At the next level, from nodes 2 and 3, we see node 4 (the rightmost node).

Here’s the Python implementation of the approach described:
```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root):
    if not root:
        return []
    right_side = []
    queue = deque([root])
    
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            # If it's the last node in this level, add to right side view
            if i == level_length - 1:
                right_side.append(node.val)
            # Enqueue right child first, then left child
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
    return right_side
```

The time complexity of this solution is **O(n)**, where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the BFS traversal. The space complexity is also **O(n)** in the worst case, where we may store all nodes in the queue if the tree is skewed (e.g., a linked list). In a balanced tree, the space complexity would be **O(w)**, where w is the maximum width of the tree.

1. **Empty Tree:** If the root is None, the output should be an empty list `[]`.
2. **Single Node:** If the tree consists of only one node, the output should be `[node.val]`.
3. **All Left Children:** In a tree where every node has only a left child, the output should be the values of all nodes, as they are all visible from the right side.
4. **Balanced Tree:** In a balanced tree, ensure that the correct rightmost nodes are captured at each level.

Binary Tree Right Side View

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string