【Video】BFS solution
This article explains a solution for the problem of traversing a binary tree level by level, known as the Binary Tree Level Order Traversal problem. Using bread
This article explains a solution for the problem of traversing a binary tree level by level, known as the **Binary Tree Level Order Traversal** problem. Using breadth-first search (BFS) and a queue, this approach efficiently collects all node values at each depth of the tree.

# Solution Video

https://youtu.be/upSho7muH-0

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

Subscribers: 12,141
Thank you for your support!

---



#### Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level.)

---

### Code Overview

Here is the solution:

```python
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        if not root:
            return res
        
        q = collections.deque()
        q.append(root)
    
        while q:
            same_level = []

            for _ in range(len(q)):
                node = q.popleft()
                same_level.append(node.val)

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            res.append(same_level)
        
        return res
```

Let’s break this code down step by step to understand how it works.

---

### Step-by-Step Explanation

#### 1. Edge Case: Empty Tree

The first condition checks if the root of the binary tree is `None`. If so, the function immediately returns an empty list since there are no levels to traverse.

```python
if not root:
    return res
```

#### 2. Initialize the Queue

The queue `q` (implemented using `collections.deque`) is initialized with the root node of the binary tree. This queue will help us process nodes level by level.

```python
q = collections.deque()
q.append(root)
```

#### 3. BFS Traversal

The BFS traversal uses a `while` loop that continues until the queue is empty. Inside the loop:

1. **Track Nodes at the Same Level**:
   - A temporary list, `same_level`, is created to store node values for the current level.

2. **Process Nodes in the Queue**:
   - For each node in the current level (determined by `len(q)`), we:
     - Remove the node from the queue (`q.popleft()`).
     - Append its value to `same_level`.
     - Add its left and right children (if they exist) to the queue.

3. **Store Level Values**:
   - After processing all nodes in the current level, `same_level` is appended to the result list `res`.

```python
while q:
    same_level = []

    for _ in range(len(q)):
        node = q.popleft()
        same_level.append(node.val)

        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

    res.append(same_level)
```

#### 4. Return Result

Finally, the result list `res`, which contains values for all levels, is returned.

```python
return res
```

---

https://youtu.be/pCc4kR-TdYs

### Visualization

#### Example Input

Consider the binary tree:

```
        3
       / \
      9   20
         /  \
        15   7
```

#### Execution Walkthrough

1. **Initialization**:
   - `q = deque([3])`
   - `res = []`

2. **Level 1**:
   - `same_level = [3]`
   - Append left (9) and right (20) children of 3 to the queue.
   - Update: `res = [[3]]`, `q = deque([9, 20])`

3. **Level 2**:
   - `same_level = [9, 20]`
   - Append left (15) and right (7) children of 20 to the queue.
   - Update: `res = [[3], [9, 20]]`, `q = deque([15, 7])`

4. **Level 3**:
   - `same_level = [15, 7]`
   - Update: `res = [[3], [9, 20], [15, 7]]`, `q = deque([])`

5. **Queue Empty**:
   - The loop exits, and `res` is returned.

---

### Complexity Analysis

1. **Time Complexity**:
   - Each node is visited exactly once, so the time complexity is \(O(n)\), where \(n\) is the number of nodes in the tree.

2. **Space Complexity**:
   - The queue stores at most one level of the tree at any time. In the worst case (a balanced tree), this is \(O(w)\), where \(w\) is the maximum width of the tree.

---

### Key Takeaways

- **Breadth-First Search**: BFS is a natural choice for problems involving level order traversal of trees.
- **Queue-Based Approach**: Using a queue ensures nodes are processed level by level in a FIFO order.
- **Scalability**: This algorithm is efficient and handles trees of any shape or size.

Understanding this approach equips you with a foundational technique that extends to numerous other tree traversal problems.

---

Thank you for reading my post. Please upvote it and don't forget to subscribe to my channel!

⭐️ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

⭐️ Other Tree Problem
#98 - Validate Binary Search Tree

https://youtu.be/PITUkhnuWHQ


['Python3']