Binary Tree Level-Order Traversal (BFS)

medium tree bfs queue

Problem

Given the root of a binary tree, return the values of every node visited level by level from left to right. The classical breadth-first walk uses a queue.

Inputtree = [A, B, C, D, E, _, F]

Output[A, B, C, D, E, F]

Level-order layout (root first, "_" = missing): A → [B, C], B → [D, E], C → [_, F].

tree (level-order, "_" or "null" = missing)

from collections import deque

def level_order(root):
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return out

function levelOrder(root) {
  if (!root) return [];
  const out = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    out.push(node.val);
    if (node.left)  queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return out;
}

class Solution {
    public List<Integer> levelOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            out.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return out;
    }
}

vector<int> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<int> out;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        out.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return out;
}

Time: O(n) Space: O(n)