15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Level order traversal visits a tree level by level, left to right, using a queue. Dequeue the front node, record its value, then enqueue its left and right children at the rear. Every node is enqueued and dequeued once, so time is O(n). The queue holds O(w) nodes, where w is the widest level.
| Data structure | A FIFO queue of discovered, unprocessed nodes |
|---|---|
| Order on the example | [A, B, C, D, E] |
| Time | O(n) |
| Queue space | O(w), w is the widest level; O(n) worst case |
| Visited set | Not needed, a tree has no cycles |
Assume you can identify a tree’s root, children, and depth. Depth-first traversals move down one branch before returning.
Breadth-first traversal moves across a tree level by level, starting at the root. For a rooted tree, this order is also called level-order traversal.
Use a queue. A queue is first-in, first-out:
For a proper tree, no visited set is needed when following child links. A tree has no cycles, and each non-root node has one parent, so each node is discovered through one parent.
Use this tree throughout the lesson:
1 A
2 / \
3 B C
4 / \
5 D EA is the root.B and C are at depth 1.D and E are at depth 2.Level-order traversal visits every node at one depth before moving to the next depth:
1[A, B, C, D, E]Start with only the root discovered.
1Front Rear
2 [ A ]
3
4output: []The queue holds nodes waiting to be processed. The output holds values from nodes already processed.
A BFS iteration follows this order:
Process the current node first. Then place its children at the rear, behind nodes already waiting.
The root exists, so enqueue it.
1Front Rear
2 [ A ]
3
4output: []Dequeue A. Append A to the output. Then enqueue B, followed by C.
BFS dequeues A, B, C, D, E in that order. Children join the rear of the queue, so every node of one level finishes before any node of the next level.
B is ahead of C because B was enqueued first.
Dequeue B. Append B. Then enqueue D, followed by E.
1dequeued: B
2
3Front Rear
4 [ C | D | E ]
5
6output: [A, B]Queue order after processing B:
C was already waiting at depth 1.D and E are at depth 2.C remains ahead of both D and E.Dequeue C. Append C. Node C has no children, so nothing is enqueued.
All depth-1 nodes have now been processed. Only depth-2 nodes remain.
Dequeue D. Append D. It has no children.
1dequeued: D
2
3Front Rear
4 [ E ]
5
6output: [A, B, C, D]Dequeue E. Append E. It has no children.
1dequeued: E
2
3Front Rear
4 [ ]
5
6output: [A, B, C, D, E]The queue is empty, so traversal stops.
Look at the queue just before each dequeue:
1Before dequeuing A: [A]
2Before dequeuing B: [B, C]
3Before dequeuing C: [C, D, E]
4Before dequeuing D: [D, E]
5Before dequeuing E: [E]The queue always contains exactly the nodes that have been discovered but not yet processed.
It also has a useful order:
The loop invariant is:
Before each dequeue, the queue lists exactly the discovered but unprocessed nodes in nondecreasing depth order; nodes at the same depth occur left to right according to child enqueue order.
The queue [C, D, E] shows both parts:
C is at depth 1, so it comes before D and E at depth 2.D comes before E because B’s left child was enqueued before its right child.Start with the boundary case.
If the root is null, there is no node to process. Return an empty traversal immediately. Do not enqueue a null root.
For a non-empty tree:
Enqueue the left child before the right child. That choice gives a deterministic left-to-right order within each level.
Input: root, the root node of a binary tree, or null. Each node has value, left, and right fields.
Return value: A new list containing node values in breadth-first order.
Mutation behavior: Does not change the tree. It mutates only its local queue and local output list.
Queue helper contract: enqueue(queue, item) adds item at the rear. dequeue(queue) removes and returns the front item. isEmpty(queue) is true exactly when the queue has no items.
11 function levelOrder(root):
22 output <- empty list
33
44 if root = null:
55 return output
66
77 queue <- empty queue
88 enqueue(queue, root)
99
1010 while not isEmpty(queue):
1111 current <- dequeue(queue)
1212 append current.value to output
1313
1414 if current.left != null:
1515 enqueue(queue, current.left)
1616
1717 if current.right != null:
1818 enqueue(queue, current.right)
1919
2020 return outputThe queue stores nodes, not just values. After dequeuing a node, the algorithm needs that node’s left and right links to discover children.
Use the same tree:
1 A
2 / \
3 B C
4 / \
5 D E| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 2 | Create output | [] | [] |
| 4 | Check whether root = null | [] | [] |
| 7 | Create queue | [] | [] |
| 8 | Enqueue A | [A] | [] |
| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 10 | Queue is not empty | [A] | [] |
| 11 | Dequeue A; current = A | [] | [] |
| 12 | Append A | [] | [A] |
| 14 | A.left is B, not null | [] | [A] |
| 15 | Enqueue B | [B] | [A] |
| 17 | A.right is C, not null | [B] | [A] |
| 18 | Enqueue C | [B, C] | [A] |
| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 10 | Queue is not empty | [B, C] | [A] |
| 11 | Dequeue B; current = B | [C] | [A] |
| 12 | Append B | [C] | [A, B] |
| 14 | B.left is D, not null | [C] | [A, B] |
| 15 | Enqueue D | [C, D] | [A, B] |
| 17 | B.right is E, not null | [C, D] | [A, B] |
| 18 | Enqueue E | [C, D, E] | [A, B] |
| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 10 | Queue is not empty | [C, D, E] | [A, B] |
| 11 | Dequeue C; current = C | [D, E] | [A, B] |
| 12 | Append C | [D, E] | [A, B, C] |
| 14 | C.left is null | [D, E] | [A, B, C] |
| 17 | C.right is null | [D, E] | [A, B, C] |
Lines 15 and 18 do not run because C has no children.
| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 10 | Queue is not empty | [D, E] | [A, B, C] |
| 11 | Dequeue D; current = D | [E] | [A, B, C] |
| 12 | Append D | [E] | [A, B, C, D] |
| 14 | D.left is null | [E] | [A, B, C, D] |
| 17 | D.right is null | [E] | [A, B, C, D] |
| Pseudocode line | Action | Queue, front to rear | Output |
|---|---|---|---|
| 10 | Queue is not empty | [E] | [A, B, C, D] |
| 11 | Dequeue E; current = E | [] | [A, B, C, D] |
| 12 | Append E | [] | [A, B, C, D, E] |
| 14 | E.left is null | [] | [A, B, C, D, E] |
| 17 | E.right is null | [] | [A, B, C, D, E] |
| 10 | Queue is empty, so leave the loop | [] | [A, B, C, D, E] |
| 20 | Return output | [] | [A, B, C, D, E] |
We show that levelOrder returns the node values in level order.
If root is null, the algorithm returns []. An empty tree has no node values.
Otherwise, line 8 enqueues only the root. Before the first dequeue, the queue contains exactly the discovered but unprocessed nodes: only the root. It is also in nondecreasing depth order because it is the only node.
The invariant holds before the loop begins.
Assume the invariant is true before an iteration.
The algorithm dequeues the queue’s front node. Since the queue is in nondecreasing depth order, the front node has the smallest depth among all discovered but unprocessed nodes. The algorithm processes that node exactly once by appending its value to output.
Next, it enqueues each existing child once:
Each child is discovered after its parent is processed. Children go to the rear of the queue, behind nodes that were already discovered. Those older queue entries are at the same depth or a shallower depth. No deeper child moves ahead of an unprocessed node at a smaller depth.
For children of the same parent, left is enqueued before right, preserving left-to-right order. Across parents at the same depth, parents are dequeued left to right, so their children are also enqueued left to right.
After the iteration, the queue again contains exactly the discovered but unprocessed nodes in the required depth and left-to-right order. The invariant is preserved.
The loop ends only when the queue is empty.
Every non-null node is eventually enqueued: the root is enqueued initially, and every other node is enqueued when its parent is processed. Each node is dequeued once after it is enqueued. Because the tree has finitely many nodes, the queue eventually becomes empty.
At termination, every node has been dequeued and appended exactly once. The invariant establishes that dequeue order was level order. The returned output is the level-order traversal sequence.
Let n be the number of nodes.
Each node is:
Queue enqueue and dequeue operations take O(1) work each. The loop therefore does constant work per node, for a total time of:
1O(n)For queue space, let w be the maximum width of the tree: the largest number of nodes at any one level.
The queue can contain O(w) nodes. So auxiliary queue space is:
1O(w)A broad tree can have w proportional to n, so worst-case auxiliary queue space is:
1O(n)The returned output list stores one value per node:
1output space: O(n)Output storage is separate from the auxiliary queue space.
Incorrect assumption: A stack can manage the pending nodes.
A stack is last-in, first-out. It processes the most recently added child first, which leads down a branch rather than across a level.
Small exposing tree:
1 A
2 / \
3 B C
4 /
5 DIf the traversal pushes B, then C, a stack removes C first or, with the opposite push order, can descend to D before processing C. One exposing wrong result is:
1[A, B, D, C]But BFS order must be:
1[A, B, C, D]Correction: Use FIFO queue operations: dequeue from the front and enqueue at the rear.
Incorrect line:
1enqueue(queue, root)without checking whether root is null.
Small exposing input:
1root = nullWrong state: The queue contains null, and the algorithm attempts to process null as if it were a node.
Correction: Return [] before queue initialization, or guard the root enqueue.
1if root = null:
2 return []Incorrect order:
1if current.right != null:
2 enqueue(queue, current.right)
3
4if current.left != null:
5 enqueue(queue, current.left)Small exposing tree:
1 A
2 / \
3 B CWrong queue after processing A:
1[C, B]Wrong output:
1[A, C, B]Correction: Enqueue the left child first, then the right child.
1enqueue(queue, current.left)
2enqueue(queue, current.right)when those children exist.
Incorrect assumption: Reaching into a waiting node and enqueueing that node’s children before dequeuing the current front node is safe.
Small exposing tree:
1 A
2 / \
3 B C
4 /
5 DAfter processing A, the correct queue is:
1[B, C]Adding D before dequeuing B changes the queue based on a node that has not been processed. The queue no longer represents “discovered nodes after processing the nodes already removed from the front.” Misplaced operations can place a deeper node in an order that does not match BFS.
Correction: In every iteration, first dequeue exactly one front node. Then append its value. Then enqueue only that dequeued node’s direct children at the rear.
| Input tree | Expected output |
|---|---|
| Empty tree | [] |
Single node A | [A] |
A with only right child C | [A, C] |
A with children B, C; B has D; C has E | [A, B, C, D, E], not [A, B, D, C, E] |
Implement:
1levelOrder(root)It must return node values in BFS order.
The executable tests verify this contract:
1from collections import deque
2
3class Node:
4 def __init__(self, value, left=None, right=None):
5 self.value, self.left, self.right = value, left, right
6
7def level_order(root):
8 output = []
9 if root is None:
10 return output
11 queue = deque([root])
12 while queue:
13 current = queue.popleft() # front
14 output.append(current.value)
15 if current.left:
16 queue.append(current.left) # rear
17 if current.right:
18 queue.append(current.right)
19 print(current.value, "-> queue", "[" + ", ".join(n.value for n in queue) + "]")
20 return output
21
22root = Node("A", Node("B", Node("D"), Node("E")), Node("C"))
23print("order", "[" + ", ".join(level_order(root)) + "]")1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5
6public class Main {
7 static class Node {
8 String value;
9 Node left, right;
10 Node(String value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
11 Node(String value) { this(value, null, null); }
12 }
13
14 static List<String> levelOrder(Node root) {
15 List<String> output = new ArrayList<>();
16 if (root == null) return output;
17 Deque<Node> queue = new ArrayDeque<>();
18 queue.addLast(root);
19 while (!queue.isEmpty()) {
20 Node current = queue.pollFirst(); // front
21 output.add(current.value);
22 if (current.left != null) queue.addLast(current.left); // rear
23 if (current.right != null) queue.addLast(current.right);
24 List<String> waiting = new ArrayList<>();
25 for (Node n : queue) waiting.add(n.value);
26 System.out.println(current.value + " -> queue " + waiting);
27 }
28 return output;
29 }
30
31 public static void main(String[] args) {
32 Node root = new Node("A", new Node("B", new Node("D"), new Node("E")), new Node("C"));
33 System.out.println("order " + levelOrder(root));
34 }
35}1#include <deque>
2#include <iostream>
3#include <string>
4#include <vector>
5using namespace std;
6
7struct Node {
8 string value;
9 Node *left, *right;
10 Node(string v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
11};
12
13string fmt(const vector<string>& v) {
14 string s = "[";
15 for (size_t i = 0; i < v.size(); i++) s += (i ? ", " : "") + v[i];
16 return s + "]";
17}
18
19vector<string> levelOrder(Node* root) {
20 vector<string> output;
21 if (!root) return output;
22 deque<Node*> queue = {root};
23 while (!queue.empty()) {
24 Node* current = queue.front(); // front
25 queue.pop_front();
26 output.push_back(current->value);
27 if (current->left) queue.push_back(current->left); // rear
28 if (current->right) queue.push_back(current->right);
29 vector<string> waiting;
30 for (Node* n : queue) waiting.push_back(n->value);
31 cout << current->value << " -> queue " << fmt(waiting) << endl;
32 }
33 return output;
34}
35
36int main() {
37 Node d("D"), e("E"), c("C");
38 Node b("B", &d, &e);
39 Node root("A", &b, &c);
40 vector<string> order = levelOrder(&root);
41 cout << "order " << fmt(order) << endl;
42}1class Node {
2 constructor(value, left = null, right = null) {
3 this.value = value;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function levelOrder(root) {
10 const output = [];
11 if (root === null) return output;
12 const queue = [root];
13 let head = 0; // an index avoids the O(n) cost of shift()
14 while (head < queue.length) {
15 const current = queue[head++]; // front
16 output.push(current.value);
17 if (current.left) queue.push(current.left); // rear
18 if (current.right) queue.push(current.right);
19 const waiting = queue.slice(head).map((n) => n.value);
20 console.log(`${current.value} -> queue [${waiting.join(', ')}]`);
21 }
22 return output;
23}
24
25const root = new Node('A', new Node('B', new Node('D'), new Node('E')), new Node('C'));
26console.log(`order [${levelOrder(root).join(', ')}]`);It is BFS. Breadth-first search on a rooted tree visits nodes by depth, and that order is called level order. Preorder, inorder and postorder are the depth-first orders.
No. Preorder goes down one branch before the next, giving [A, B, D, E, C] on the example. Level order gives [A, B, C, D, E] because C waits ahead of D and E in the queue.
A stack is last in, first out, so it chases the newest child and descends a branch. A queue keeps older, shallower nodes at the front, which is what finishes one level before the next.
Treat the list as an array with null placeholders. The children of index i are at 2i + 1 and 2i + 2, so create the nodes and link them by those indices.
At the start of each pass, record the queue's current size, then process exactly that many nodes. They are one level. Children enqueued during the pass belong to the next.