Binary Tree Level Order Traversal

Return the values of a binary tree level by level, from left to right.

A way to picture it

Boarding a plane by rows. A gate agent calls everyone in the current row (however many are waiting right now), and each person who boards sends their children to the back of the line for the next call.

How to approach it

BFS with a queue. Before each level, snapshot the queue's size — exactly that many nodes belong to the current level.

Example

Input: {"root":[3,9,20,null,null,15,7]}. Output: [[3],[9,20],[15,7]].

Complexity: O(n) time and O(w) space. Each node is queued once; w is the widest level.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.