Binary Tree Level Order Traversal

medium tree bfs queue

Problem

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).

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;
}

Explanation

Level order means visiting nodes top to bottom, left to right, and a queue is the perfect tool because it serves nodes in the exact order they were added — first in, first out.

We start by putting the root in the queue. Then we loop: take the front node, record its value, and push its left and right children onto the back of the queue.

Because children always go to the back, a node's siblings and cousins on the same level are served before any deeper node. That is what produces the breadth-first, level-by-level order.

The loop ends when the queue is empty, meaning every reachable node has been visited.

Example on [A,B,C,D,E,_,F]: dequeue A (enqueue B,C), dequeue B (enqueue D,E), dequeue C (enqueue F), then D, E, F → visit order [A,B,C,D,E,F].

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