Traverse a binary tree level by level
Return a binary tree's values from top to bottom and left to right within each level.
Course progress
Problem 83 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
tree root 8; next level 4,12; final level 2,6
Expected output
8 4 12 2 6
What is happening?
A queue visits the root first, then both nodes on the second level, followed by the two nodes on the third level.
Solution strategy
Build the right mental model
Place the root in a queue, then repeatedly remove the next node and enqueue its non-null children.
Core concepts
binary tree · breadth-first search
Complexity
Time O(n), space O(w), where w is the tree's maximum width.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for level-order-tree-traversal
using System;
using System.Collections.Generic;
class Program
{
class Node
{
public int Value { get; private set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value) { Value = value; }
}
static List<int> LevelOrder(Node root)
{
var values = new List<int>();
if (root == null) return values;
var queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.Count > 0)
{
Node node = queue.Dequeue();
values.Add(node.Value);
if (node.Left != null) queue.Enqueue(node.Left);
if (node.Right != null) queue.Enqueue(node.Right);
}
return values;
}
static void Main()
{
Node root = new Node(8) {
Left = new Node(4) { Left = new Node(2), Right = new Node(6) },
Right = new Node(12)
};
Console.WriteLine(string.Join(" ", LevelOrder(root)));
}
}Knowledge check
Questions students often ask
What is the main idea behind traverse a binary tree level by level?
Place the root in a queue, then repeatedly remove the next node and enqueue its non-null children.
What is the time and space complexity of this solution?
Time O(n), space O(w), where w is the tree's maximum width.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.