Level-order traversal (BFS on a tree)

Level-order traversal starts at the root and visits all nodes at depth zero, then depth one, then depth two, and so on. On an unweighted rooted tree, this is breadth-first search (BFS). Unlike preorder, inorder and postorder, it uses a queue rather than relying on recursive depth-first calls.

Worked example

For the sample binary tree, the output is A, B, C, D, E, F, G. The queue starts with [A]. Remove A, then enqueue B and C. Remove B, then enqueue D and E. Next C enqueues F and G. This order guarantees that all nodes on an earlier level are visited before any node on the next level.

Visit order so far: –

Recursion stack: –

PreviousNext stepReset

Predict the next node before pressing Next step. Inorder depends on a defined left and right child.

Select Level order (BFS) and use Next step. The displayed queue is the frontier remaining after each visited node has enqueued its children.

Implementations

C#

C# | LevelOrder.cs

using System.Collections.Generic;

public sealed class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int value) => Value = value;
}

static List<int> LevelOrder(Node? root)
{
    var order = new List<int>();
    if (root is null) return order;
    var queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        Node node = queue.Dequeue();
        order.Add(node.Value);
        if (node.Left is not null) queue.Enqueue(node.Left);
        if (node.Right is not null) queue.Enqueue(node.Right);
    }
    return order;
}

C++

C++ | LevelOrder.cpp

#include <memory>
#include <vector>

struct Node {
    int value;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : value(value) {}
};

#include <queue>
std::vector<int> levelOrder(const Node* root) {
    std::vector<int> order;
    if (!root) return order;
    std::queue<const Node*> queue;
    queue.push(root);
    while (!queue.empty()) {
        const Node* node = queue.front(); queue.pop();
        order.push_back(node->value);
        if (node->left) queue.push(node->left.get());
        if (node->right) queue.push(node->right.get());
    }
    return order;
}

Complexity

Time is O(n) for n tree nodes. The queue holds at most a level’s worth of nodes, giving O(w) extra queue space for maximum width w (which is at most O(n)). Storing the completed order adds O(n) output space. The input tree is not included in auxiliary space.

Trees versus graphs

A rooted tree has a unique parent path to each node, so no visited set is needed if you only follow child links. In a general graph, cycles and converging paths can cause repeat visits unless you mark discovered vertices; the graph BFS guide explains the difference.

Exercise: Draw three levels of a tree and predict the queue contents after removing the root. What changes if you enqueue the right child before the left child?