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

https://algo.monster/problems/binary_tree_level_order_traversal

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;

    var queue = new LinkedList<Node<int>>();
    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();
            newLevel.Add(node.val);
            // enqueue non-null children
            if (node.left != null) queue.AddFirst(node.left);
            if (node.right != null) queue.AddFirst(node.right);
        }
        res.Add(newLevel);
    }

    return res;
}

C# Using Queue instead of LinkedList:

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();
            newLevel.Add(node.val);
            // enqueue non-null children
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        res.Add(newLevel);
    }

    return res;
}

LC (medium): https://leetcode.com/problems/binary-tree-level-order-traversal

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();
        Queue<Node<Integer>> q = new LinkedList();
        q.add(root);
        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;
                lst.add(n.val);
                q.add(n.left);
                q.add(n.right);
            }
            if(lst.size() > 0)
            {
                //System.out.println(lst);
                result.add(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?