# Binary Tree Level Order Traversal - Breadth First Search / BFS on Tree

a more intuitive python solution for me, would this be ok too?

def level_order_traversal(root: Node) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
q = deque([(root, 0)])
res = []
while q:
node, level = q.popleft()
if res and level < len(res):
res[level].append(node.val)
else:
res.append([node.val])
if node.left:
q.append((node.left, level + 1))
if node.right:
q.append((node.right, level + 1))
return res

A more intuitive solution to me:

def level_order_traversal(root: Node) → List[List[int]]:
res = []
remaining = [(root, 0)]
while remaining:
e, l = remaining.pop(0)
if l > len(res) - 1:
res.append([e.val])
else:
res[l].append(e.val)
if e.left:
remaining.append((e.left, l+1))
if e.right:
remaining.append((e.right, l+1))
return res

I find this variation a bit more intuitive

```def level_order_traversal(root: Node) -> List[List[int]]:
res = []
marker = None
queue = deque([root, marker])
level = []

while len(queue) > 1:
node = queue.popleft()
if node != marker:
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
else:
queue.append(marker)
res.append(level)
level = []
res.append(level)
return res
```

c# implementation using LinkedList as a FIFO Deque

``````public static List<List<int>> LevelOrderTraversal(Node<int> root)
{
var res = new List<List<int>>();
if (root == null) return res;

queue.AddFirst(root);  // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{  // as long as there is element in the queue
int n = queue.Count;
var newLevel = new List<int>();
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Last.Value;
queue.RemoveLast();
// enqueue non-null children
}
}

return res;
}
``````

``````public static List<List<int>> LevelOrderTraversal(Node<int> root)
{
var res = new List<List<int>>();
if (root == null) return res;

var queue = new Queue<Node<int>>();
queue.Enqueue(root);  // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{  // as long as there is element in the queue
int n = queue.Count;
var newLevel = new List<int>();
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Dequeue();
// enqueue non-null children
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
}

return res;
}
``````

How about keeping track of level explicitly?

``````
def level_order_traversal(root: Node) -> List[List[int]]:
res = []
root.level = 0
d = deque([root])
while len(d) > 0:
n = d.popleft()
for child in [n.left, n.right]:
if child:
child.level = n.level + 1
d.append(child)
if len(res) < n.level + 1:
res.append([n.val])
else:
res[n.level].append(n.val)
return res

``````

you are welcome

``````public static List<List<Integer>> levelOrderTraversal(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
List<List<Integer>> result = new ArrayList();
while(!q.isEmpty())
{
List<Integer> lst = new ArrayList();
int size = q.size();
for(int i = 0; i < size; i++)
{
Node<Integer> n = q.remove();
if(n == null) continue;
}
if(lst.size() > 0)
{
//System.out.println(lst);
}
}
return result;
}
``````

Very good queue’s content analysis resulting in a compact solution.

My solution in js:

``````function levelOrderTraversal(root) {
const numbers = []
const queue = [[root, 0]]

while(queue.length) {
const [node, lvl] = queue.shift()

if (!numbers[lvl])
numbers[lvl] = [node.val]
else
numbers[lvl].push(node.val)

if (node.left)
queue.push([node.left, lvl + 1])

if (node.right)
queue.push([node.right, lvl + 1])
}
return numbers
}
``````

is the graphic for the explanation missing a slide?

is the graphic for the explanation missing a slide?

IMO, this solution appears to be easier to understand:

``````def level_order_traversal(root: Node) -> List[List[int]]:
if not root:
return []

res = []
queue = deque([root])

while queue:
level_nodes = []

for _ in range(len(queue)):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_nodes)

return res
``````

Another possible approach:

``````def level_order_traversal(root: Node) -> List[List[int]]:
if not root:
return []

res = []
queue = deque([root])

while queue:
level_nodes = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level_nodes.append(node.val)
queue.append(node.left)
queue.append(node.right)

if level_nodes:
res.append(level_nodes)

return res
``````

I am amazed by the answer’s approach, which demonstrates a deep understanding of the fact that each `while` loop indicates a new level.

``````def level_order_traversal(root: Node) -> List[List[int]]:
q = deque([(root, 0)])
rst = []
while len(q):
node, level = q.popleft()
if not node:
continue
if level >= len(rst):
rst.append([node.val])
else:
rst[level].append(node.val)

q.append((node.left, level + 1))
q.append((node.right, level + 1))
return rst
``````