Coding problem · Medium · Trees

Binary Tree Level Order Traversal

Medium Algorithms & data structures Most askedSeen at Amazon, Meta, Microsoft, LinkedIn

Given the root of a binary tree, return the level order traversal of its values: a list of levels, each listing values from left to right.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Hints

Hint 1

Use a queue. Process exactly the nodes currently in the queue to build one level.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(w) where w is the widest level

Breadth-first search with a queue: at the start of each round, the queue holds exactly one level. Pop that many nodes, record their values, and enqueue their children.

Reference solution

function levelOrder(root) {
  const out = [];
  let level = root ? [root] : [];
  while (level.length) {
    out.push(level.map((n) => n.val));
    level = level.flatMap((n) => [n.left, n.right].filter(Boolean));
  }
  return out;
}

function levelOrder(root: TreeNode | null): number[][] {
  const out: number[][] = [];
  let level: TreeNode[] = root ? [root] : [];
  while (level.length) {
    out.push(level.map((n) => n.val));
    level = level.flatMap((n) => [n.left, n.right].filter((c): c is TreeNode => c !== null));
  }
  return out;
}

from collections import deque

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    out = []
    queue = deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            queue.extend(c for c in (node.left, node.right) if c)
        out.append(level)
    return out

<?php

function levelOrder(?TreeNode $root): array
{
    $out = [];
    $level = $root ? [$root] : [];
    while ($level) {
        $out[] = array_map(fn($n) => $n->val, $level);
        $next = [];
        foreach ($level as $n) {
            if ($n->left) $next[] = $n->left;
            if ($n->right) $next[] = $n->right;
        }
        $level = $next;
    }
    return $out;
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode n = queue.poll();
                level.add(n.val);
                if (n.left != null) queue.add(n.left);
                if (n.right != null) queue.add(n.right);
            }
            out.add(level);
        }
        return out;
    }
}

Follow-up questions

Zigzag order
Right side view (last value of each level)

Maximum Depth of Binary Tree · Easy
Invert Binary Tree · Easy
Validate Binary Search Tree · Medium
Lowest Common Ancestor of a BST · Medium