Trees· 10 min

Level-order Traversal

BFS using a queue — level by level

Setup

Step 1 / 22

Current step

1 / 22

Start level-order (BFS): enqueue the root 50. Queue: [50]

Step log

7 nodes · depth 3 · drag to pan, scroll to zoom
Current / on path
Visited
Just inserted
Found
levelorder_traversal.java
1void levelorder(Node root) {
2    Queue<Node> q = new ArrayDeque<>(List.of(root));
3    while (!q.isEmpty()) {
4        Node n = q.poll();
5        visit(n);
6        if (n.left != null) q.add(n.left);
7        if (n.right != null) q.add(n.right);
8    }
9}
● Java
Queue (FIFO)1 frame
node 50next out
Traversal output0 / 7

nothing visited yet

Level-order Traversal

Level-order traversal visits every node in a specific order. Level-order (BFS) visits nodes level by level using a queue.

Nodes
7
Mode
traversal
Time (avg)
O(log n)
Time (worst)
O(n)
50307020406080
23 / 46