Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Python DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.py

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def render(node):
    if node is None:
        return "_"
    if node.left is None and node.right is None:
        return str(node.value)
    return f"{node.value}({render(node.left)},{render(node.right)})"

def sample_tree():
    n1 = Node(1)
    n3 = Node(3)
    n2 = Node(2, n1, n3)
    n5 = Node(5)
    n7 = Node(7)
    n6 = Node(6, n5, n7)
    return Node(4, n2, n6)

from collections import deque
root = sample_tree()
queue = deque([root])
output = []
while queue:
    node = queue.popleft()
    output.append(node.value)
    if node.left is not None:
        queue.append(node.left)
    if node.right is not None:
        queue.append(node.right)
print(output)

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Render tree structure explicitly instead of printing node objects.
The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.

level order Level-order traversal uses a queue to visit shallower nodes first.