Binary Tree Level Order Traversal

Medium
1905.

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Given the root of a binary tree, return its node values level by level: one list per level, from the root's level down, each list reading its level from left to right.

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]
Explanation
Level 1 holds 3, level 2 holds 9 and 20, level 3 holds 15 and 7.

Example 2

Input
root = [1]
Output
[[1]]
Explanation
A single node is a single level.

Example 3

Input
root = []
Output
[]
Explanation
An empty tree has no levels.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Level Order Traversal — Problem & Solution

Binary Tree Level Order Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Level Order Traversal is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Problem statement

Given the root of a binary tree, return its node values level by level: one list per level, from the root's level down, each list reading its level from left to right.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Explanation: Level 1 holds 3, level 2 holds 9 and 20, level 3 holds 15 and 7.

Example 2

Input: root = [1]
Output: [[1]]
Explanation: A single node is a single level.

Example 3

Input: root = []
Output: []
Explanation: An empty tree has no levels.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= Node.val <= 1000

Hints for Binary Tree Level Order Traversal

  1. Hint 1

    A queue hands nodes back in the order they were added — add children left before right and the nodes come out level after level.

  2. Hint 2

    The difficulty is knowing where one level ends and the next begins.

  3. Hint 3

    At the start of each level the queue holds exactly that level: read its size first, then take exactly that many nodes into one list.

How to solve Binary Tree Level Order Traversal

Breadth-first search with a queue visits nodes in level order; fixing the queue's size at the start of each round separates the levels.

Approach

  1. If the tree is empty, return an empty list.
  2. Put the root in a queue.
  3. While the queue is not empty: let size be its length, take size nodes from the front, append their values to a new list and push each one's left then right child.
  4. Append that list to the answer and repeat.

Why it works

By induction, when a round starts the queue holds exactly the nodes of one level in left-to-right order: the round removes all of them and adds exactly their children, in left-to-right order, which is the next level.

Complexity

  • Time — O(n)
  • Space — O(w), w the largest number of nodes on one level (plus the output)

Pitfalls

  • Read the queue's size before the inner loop — it grows while children are added.
  • Return [], not [[]], for an empty tree.

Reference solution

Python

from typing import List, Optional

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    out = []
    level = [root] if root else []
    while level:
        out.append([node.val for node in level])
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    return out

Java

public static int[][] levelOrder(TreeNode root) {
    List<int[]> out = new ArrayList<>();
    Deque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        int[] row = new int[size];
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            row[i] = node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        out.add(row);
    }
    return out.toArray(new int[0][]);
}

C++

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

JavaScript

var levelOrder = function(root) {
    var out = [];
    if (root === null) return out;
    var queue = [root], head = 0;
    while (head < queue.length) {
        var end = queue.length, row = [];
        while (head < end) {
            var node = queue[head++];
            row.push(node.val);
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals