Level order traversal (BFS)

Visit the tree level by level, left to right, using a queue.

Time O(n)Space O(w)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A queue is first in, first out. Children join the back of the line, so every node on one level is processed before any node on the next.

Code

C++PythonC#

vector<int> levelOrder(TreeNode* root) {
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        result.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return result;
}

from collections import deque

def level_order(root: TreeNode) -> list[int]:
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

public static List<int> LevelOrder(TreeNode root) {
    var result = new List<int>();
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    while (queue.Count > 0) {
        TreeNode node = queue.Dequeue();
        result.Add(node.val);
        if (node.left != null) queue.Enqueue(node.left);
        if (node.right != null) queue.Enqueue(node.right);
    }
    return result;
}

Tips

w is the widest level, which can be n/2 in a full tree.
To group by level, read queue.Count at the start of each round and dequeue exactly that many nodes.

In the .NET library

Queue<T> is the BFS workhorse: Enqueue adds at the back, Dequeue removes from the front, both O(1).