⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#102) before relying on it.

Binary Tree Level Order Traversal

An interactive visualization of Breadth-First Search on a binary tree. Watch nodes being processed level by level using a queue, building the result array as each level completes.

BFS LeetCode 102 ↗ Medium

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

The tree is given as an array in level-order format, where null represents a missing node. Return a list of lists, where each inner list contains the values of nodes at that depth level.

Interactive Visualization

Tree (level-order array)

Preset

Speed:

Tree Visualization

BFS Queue (front → back)

Empty

Result

[]

Code

fun levelOrder(root: TreeNode?): List<List<Int>> {    if (root == null) {        return emptyList()    }    val result = mutableListOf<List<Int>>()    val queue: ArrayDeque<TreeNode> = ArrayDeque()    queue.add(root)    while (queue.isNotEmpty()) {        val levelSize = queue.size        val level = mutableListOf<Int>()        for (i in 0 until levelSize) {            val node = queue.removeFirst()            level.add(node.`val`)            node.left?.let { queue.add(it) }            node.right?.let { queue.add(it) }        }        result.add(level)    }    return result}

def levelOrder(root):    if not root:        return []    result = []    queue = deque([root])    while queue:        level_size = len(queue)        level = []        for i in range(level_size):            node = queue.popleft()            level.append(node.val)            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        result.append(level)    return result

Status

Press Step or Play to begin.

How It Works

Key Insight

Level order traversal processes a tree breadth-first — visiting all nodes at depth 0, then all at depth 1, and so on. A queue naturally gives us this order: we enqueue children as we process parents. The trick is tracking where one level ends and the next begins by capturing len(queue) at the start of each level.

The Algorithm

Initialize: Create a queue with the root node. Create an empty result list.
Outer loop: While the queue is not empty, a new level begins.
Capture level size: level_size = len(queue) — this is how many nodes are at the current level.
Inner loop: Process exactly level_size nodes from the front of the queue.
For each node: Dequeue it, record its value, then enqueue its left and right children (if they exist).
After the inner loop: Append the collected level values to the result.
Repeat until the queue is empty — all levels have been processed.

Complexity

Time O(n)

Space O(n)

Every node is enqueued and dequeued exactly once, giving O(n) time. The queue holds at most one full level of the tree at a time — in a complete binary tree the last level has ~n/2 nodes, so space is O(n).