Introduction

Breadth-first traversal prints a tree level by level, starting at the root and moving outward. The catch is that level order traversal is defined by a frontier of nodes, and remembering that frontier is exactly where the space cost comes from.

Why Normal BFS Uses Extra Space

For a general binary tree, the standard BFS algorithm keeps a queue of nodes that have been discovered but not printed yet. That queue may hold an entire level of the tree. In a wide tree, that can be many nodes, so the extra space is O(w), where w is the maximum width of the tree.

That is not an implementation accident. It is the information the algorithm needs. After you print one parent, you still must remember its sibling, its cousin, and all other nodes waiting at the same level. If the tree is read-only and each node only has left and right pointers, there is no place to store that frontier except in an external data structure.

This is why a true linear-time BFS with O(1) extra space is generally not available for an ordinary binary tree. Claims that Morris traversal solves this are usually mixing up depth-first traversal with breadth-first traversal. Morris traversal is excellent for inorder-style walks, but level order has different bookkeeping requirements.

The Correct Queue-Based Solution

If you need BFS on a normal tree, use a queue. It is simple, correct, and optimal for the standard model.

1from collections import deque
2
3
4class Node:
5    def __init__(self, value, left=None, right=None):
6        self.value = value
7        self.left = left
8        self.right = right
9
10
11def print_bfs(root):
12    if root is None:
13        return
14
15    queue = deque([root])
16
17    while queue:
18        node = queue.popleft()
19        print(node.value)
20
21        if node.left is not None:
22            queue.append(node.left)
23        if node.right is not None:
24            queue.append(node.right)
25
26
27tree = Node(
28    1,
29    Node(2, Node(4), Node(5)),
30    Node(3, None, Node(6)),
31)
32
33print_bfs(tree)

This prints:

11
22
33
44
55
66

Time complexity is O(n) because each node is enqueued and dequeued once. Extra space is O(w), which is the right answer for general BFS.

When O(1) Space Becomes Possible

People sometimes ask for O(1) space because they are willing to change the problem slightly. Under those changed constraints, a constant-space approach may exist.

One option is to modify the tree while traversing it. For example, if nodes already contain parent pointers, sibling links, or spare fields that can temporarily act as next-level links, you can sometimes walk one level and stitch together the next. Another option is to accept worse running time. You can print level 0, then level 1, then level 2, repeatedly scanning from the root. That avoids a queue, but it re-traverses the tree many times and is usually O(nh) instead of O(n), where h is the height.

A third case is a specialized tree structure. Perfect binary trees with next pointers, threaded trees, or custom node layouts can support level-order-style output with very little auxiliary memory because the needed links already exist in the data structure.

So the right question is not only "Can BFS be O(1) space?" but also "What model are we allowed to use?" On a plain binary tree with only child pointers and no destructive updates, the practical answer is no.

Practical Decision Rule

Use queue-based BFS when:

• the tree is ordinary and read-only
• you want O(n) time
• correctness and maintainability matter more than clever pointer tricks

Consider a specialized constant-space technique only when:

• the node structure already includes extra links
• temporary mutation is acceptable
• the input is a restricted tree shape
• you can tolerate more complicated logic or slower running time

Common Pitfalls

Trying to force Morris traversal into BFS is the most common mistake. Morris traversal removes stack usage for certain depth-first traversals, but it does not magically preserve a whole level frontier.

Another mistake is saying BFS needs O(h) space because trees have height h. That is true for DFS recursion, not BFS. The important quantity for BFS is width, not height.

A third problem is mutating pointers without a safe restoration plan. If you temporarily repurpose left or right, you can easily corrupt the tree and create subtle bugs later.

Summary

• Standard BFS on a general binary tree uses a queue and O(w) extra space.
• True O(1) extra-space BFS is generally not possible on a read-only tree with only child pointers.
• Morris traversal helps with some depth-first traversals, not ordinary level-order traversal.
• Constant-space variants require changed assumptions such as mutation, extra links, or slower repeated scans.
• In production code, the queue-based solution is usually the right one.