Binary tree left side view

Return the leftmost node at each depth of a binary tree.

binary-tree levels bfs dfs

Write a function `left_side_view(root)` that takes the root of a binary tree and returns a list of the leftmost value at each depth level, from the root level down to the deepest level.

Each node is represented as a dictionary with keys `val`, `left`, and `right`. If a child is missing, it is `None`. The tree may be empty (root is `None`), in which case return an empty list.

The order of the returned list must correspond to increasing depth (level 0 first). There will be exactly one leftmost value per depth level.

Constraints

The number of nodes is between 0 and 10^4. Node values are integers within [-10^5, 10^5]. The tree is a valid binary tree. Time complexity should be O(N) where N is the number of nodes.

Example

```python
# Example 1
# Tree: 1 -> left: 2, right: 3
#       2 -> left: 4
#       3 -> right: 5
root = {"val": 1, "left": {"val": 2, "left": {"val": 4, "left": None, "right": None}, "right": None}, "right": {"val": 3, "left": None, "right": {"val": 5, "left": None, "right": None}}}
left_side_view(root)
# Expected: [1, 2, 4]

# Example 2
# Tree: root = None
left_side_view(None)
# Expected: []
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think BFS: traverse level by level and take the first node of each level.

Alternatively, DFS with depth tracking: update the first node seen at each depth.

Remember to handle the empty tree case.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.