Trees

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.

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

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
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)

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1class Node:2    def __init__(self, value, left=None, right=None):
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    24root = sample_tree()25queue = deque([root])26output = []
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. print(output)

    33        queue.append(node.right)34print(output)
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

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

Implementation notes

  • Python stores the tree as Node objects with value, left, and right attributes, where missing children are None. The traversal keeps object references in a collections.deque, starting with deque([root]).
  • Each loop iteration uses queue.popleft() to remove the current node from the front and queue.append(...) to enqueue non-None children at the back, avoiding the shifting cost a list would pay for pop(0).
  • output is a Python list mutated with append(node.value). The trace shows both replay-visible containers after every dequeue, such as queue [6, 1, 3] with output [4, 2], until the queue is empty.
  • The traversal allocates the deque and result list; those containers and the node objects are managed by Python while references to them remain.