🔥[EASY] BFS in Python, Java, C++, JavaScript - Detailed Explanation with Examples
IntuitionThis question asks us to do a level traversal of a binary tree. We can acheive this by performing BFS (Breadth First Search).ApproachWe will perform a
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
This question asks us to do a level traversal of a binary tree. We can acheive this by performing **BFS** (Breadth First Search).
# Approach
<!-- Describe your approach to solving the problem. -->
We will perform a simple level order traversal using a queue. 

**Here's how:**

We will keep track of the levels by adding a `null` to the queue on the end of each level. Lets take an example

![Screenshot 2024-12-30 at 16-03-16 Binary Tree Level Order Traversal - LeetCode.png](https://assets.leetcode.com/users/images/f15e7496-34a2-4ad5-82fb-89d57ab97414_1735554802.432993.png)

Here for 3 we will add 3 to the queue and a null after it to denote the end of the level (we do this only for the root node)
`Queue: [3, null]`
Now, we will dequeue (remove the first element of the queue) and store its value in `currNode` variable.

**If the `currNode` is not null** which means we haven't hit the end of the level yet so **we will push its value in `currLevel` array** and then we check if it has a left node, if yes we add it to the queue, same for the right node.
`Queue : [null, 9, 20]`

Now we dequeue null which means **we have hit the end of the level** and our `currLevel` array contains the items of the previous level so, **we push it to the `ans` array and empty the `currLevel` array.** Now since the values of next level have already been added to the queue **we add `null` to the queue to denote the end of prevous level.**
`Queue : [9, 20, null]`
`ans : [[3]]`

Now, we dequeue 9, add it to the currLevel array and if it has any child, we add it to the queue, since it doesn't we add nothing
`Queue : [20, null]`
`currLevel: [9]`

We repeat this till the end. When our queue looks like this: `[7, null]` now when we dequeue 7 and push the `currLevel` to the `ans`
our answer is complete but in the next iteration we dequeue `null` our queue will be empty so, we need to stop the loop. We add a condition for this.
```
If currNode == null {
    (some stuff)    
    if (queue is empty) {
        break
    } else {
        queue.enqueue(null)
    } 
}
```

# Complexity
- Time complexity: **O(n)**: Every node is visited exactly once.

- Space Complexity: **O(w)**: The maximum width of the tree (number of nodes in the largest level) determines the maximum size of the queue.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
In languages (like JavaScript) which do not have queues we can implement a custom queue.

```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 levelOrder(root):
    if root is None:
        return []

    q = deque()
    q.append(root)
    q.append(None)  # Marker for end of level
    ans = []
    curr_level = []

    while q:
        curr_node = q.popleft()
        if curr_node is None:
            ans.append(curr_level)
            curr_level = []
            if not q:
                break
            else:
                q.append(None)
        else:
            curr_level.append(curr_node.val)
            if curr_node.left:
                q.append(curr_node.left)
            if curr_node.right:
                q.append(curr_node.right)

    return ans


```
``` cpp []
#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> levelOrder(TreeNode* root) {
    if (root == nullptr) return {};

    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr); // Marker for end of level
    vector<vector<int>> ans;
    vector<int> currLevel;

    while (!q.empty()) {
        TreeNode* currNode = q.front();
        q.pop();

        if (currNode == nullptr) {
            ans.push_back(currLevel);
            currLevel.clear();
            if (q.empty()) break;
            q.push(nullptr); // Marker for the next level
        } else {
            currLevel.push_back(currNode->val);
            if (currNode->left) q.push(currNode->left);
            if (currNode->right) q.push(currNode->right);
        }
    }

    return ans;
}
```
```java []
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(null); // Marker for end of level
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> currLevel = new ArrayList<>();

        while (!q.isEmpty()) {
            TreeNode currNode = q.poll();

            if (currNode == null) {
                ans.add(currLevel);
                currLevel = new ArrayList<>();
                if (q.isEmpty()) break;
                q.add(null); // Marker for the next level
            } else {
                currLevel.add(currNode.val);
                if (currNode.left != null) q.add(currNode.left);
                if (currNode.right != null) q.add(currNode.right);
            }
        }

        return ans;
    }
}
```
```javascript []
// Custom queue
 class Node {
  constructor(val) {
    this.val = val || null;
    this.next = null;
  }
}

class que {
  constructor() {
    this.first = null;
    this.last = null;
    this.length = 0;
  }

  enqueue(val) {
    let newNode = new Node(val);
    if (this.length === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.length++;
  }
  dequeue() {
    if (this.length === 0) return;
    if (this.length === 1) {
      this.last = null;
    }
    let removed = this.first.val;
    this.first = this.first.next;
    this.length--;
    return removed;
  }
}

var levelOrder = function(root) {
    if (root === null) return []
    const q = new que();
    q.enqueue(root);
    q.enqueue(null);
    let currNode;
    let ans = []
    let currLevel = []
    while (q.length > 0) {
      currNode = q.dequeue();
      if (currNode === null) {
        ans.push(currLevel)
        currLevel = []
        if (q.length === 0) {
          break;
        } else {
          q.enqueue(null);
        }
      } else {
        currLevel.push(currNode.val);
        if (currNode.left) {
          q.enqueue(currNode.left);
        }
        if (currNode.right) {
          q.enqueue(currNode.right);
        }
      }
    }
    return ans;
};

```

---


"If you found this helpful, **an upvote would mean a lot and help boost my confidence as a beginner. Thank you!**"

![Your Upvote Makes Me HAPPY!.png](https://assets.leetcode.com/users/images/f13510f0-7ba2-44ec-82e9-29089a4e379d_1735637310.9906406.png)

---




['Binary Tree', 'Python', 'C++', 'Java', 'JavaScript']