Problem

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

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

  • Select one node per level.
  • The node chosen is the first one on that level.
  • The number of visible nodes in the left-side projection matches the tree’s height, as one node is taken from each 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, 2, 5, 8, 10]

Solution

Method 1 - BFS

To solve this problem:

  1. We need to traverse the tree level by level (breadth-first search) and collect the first node from each level.
  2. A first traversal of the tree ensures visibility from the left side.
  3. This boils down to a simple BFS but paying attention to leftmost visibility at each level.

Approach

  1. Use a queue structure to perform a level-order traversal of the tree:
    • Start from the root.
    • Process each level and ensure the first node at each level is added to the result list.
  2. For each level:
    • Push all children of that node to the queue.
    • Record the value of the leftmost node only.
  3. Return the accumulated list.

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.