Problem

You are given the root of an n-ary tree, where each node may have multiple children. Imagine yourself standing on the right side of the tree. Write a program to return a list of the values of the nodes visible from the right side, ordered from top to bottom.

This is called right-hand projection of a tree. So, to simplify:

  • At each level of the tree, we select only one node.
  • The node chosen is the last one on that level.
  • The number of nodes visible in the right-hand projection matches the height of the tree, as one node is picked per level.

Examples

Example 1

graph TD
    A(1)
    A --- B(2) & C(3) & D(4)
    B --- E(5) & F(6)
	C --- G(7)
	G --- H(8) & I(9)
	I --- J(10)
  
1
2

Input: [1,[2, [5,6],3, [7, [8, 9, [10]]],4]]
Output: [1, 4, 7, 9, 10]

Solution

Method 1 - BFS

To determine the right side view, you need to traverse the tree level-by-level (often referred to as a breadth-first search or BFS). At each level:

  • Look at the last node (the right-most node) in that level.
  • Collect these nodes as they represent the right side view of the tree.

This works because the right-most node in a level is visible when viewed from the right side.

Approach

  1. Use a queue (BFS) to traverse the tree level-by-level.
  2. For each level:
    • Identify the right-most node of the level (last node traversed).
  3. Collect these right-most nodes in a result list and return it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public List<Integer> leftSideView(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                Node currentNode = queue.poll();
                if (i == 0) { // First node at each level
                    result.add(currentNode.val);
                }
                for (Node child : currentNode.children) {
                    queue.offer(child);
                }
            }
        }

        return result;
    }

    // Definition for n-ary tree Node
    static class Node {
        int val;
        List<Node> children;

        Node(int val) {
            this.val = val;
            children = new ArrayList<>();
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    class Node:
        def __init__(self, val: int):
            self.val = val
            self.children = []

    def leftSideView(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        result = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            for i in range(level_size):
                current_node = queue.popleft()
                if i == 0:  # First node at this level
                    result.append(current_node.val)
                queue.extend(current_node.children)

        return result

Complexity

  • ⏰ Time complexity: O(n). Every node is visited once in a BFS.
  • 🧺 Space complexity: O(w). The maximum space is the width of the tree at its widest level, which is proportional to the number of nodes at a level.