Level-order traversal

What is a binary tree?

A tree connects nodes in a hierarchy. The root is its starting node. A child is directly below its parent; a leaf has no children. A binary tree allows at most two children per node, called left and right. Traversal means visiting its nodes in a defined order.

Example: A root containing 8 can have a left child 4 and a right child 12. A binary tree does not automatically keep smaller values on the left: that extra rule belongs to a binary search tree.

Helpful before this chapter

If these ideas are new, begin with:

Queues and deques Recursion

Understand the idea

Level-order traversal uses a FIFO queue. To produce separate levels, capture the queue length before processing that level; newly enqueued children belong to the next level.

Work through an example

Queue [4] yields level [4]; then [2,6] yields [2,6]; then [1,3] yields [1,3].

Time and space complexity

O(n) time/O(width) queue, plus output storage.

Why it works

At a level boundary, the queue contains exactly the next level's nodes.

Common mistakes

Iterating until the queue empties inside one level mixes all levels.
list.pop(0) causes repeated shifting.

Chapter lab · Python implementation

A tree gives each non-root node one parent and contains no cycles. Our binary-tree lab combines inorder traversal, subtree height, and explicit-null serialization. Height counts edges here: empty=-1, leaf=0. Some practice problems count nodes instead; translate the convention rather than changing the recurrence blindly.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def inorder(node):
    if node is None: return []
    return inorder(node.left)+[node.value]+inorder(node.right)

def height(node):
    if node is None: return -1
    return 1+max(height(node.left),height(node.right))

def serialize(node):
    tokens=[]
    def visit(n):
        if n is None:
            tokens.append(None); return
        tokens.append(n.value)
        visit(n.left); visit(n.right)
    visit(node)
    return tokens

def deserialize(tokens):
    stream=iter(tokens)
    def build():
        value=next(stream)
        if value is None: return None
        return Node(value,build(),build())
    root=build()
    sentinel=object()
    if next(stream,sentinel) is not sentinel:
        raise ValueError('extra tokens')
    return root

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=Node(4,Node(2,Node(1),Node(3)),Node(6))
assert inorder(root)==[1,2,3,4,6]
assert height(root)==2 and height(None)==-1
assert serialize(deserialize(serialize(root)))==serialize(root)
assert serialize(None)==[None]

CHECK YOUR UNDERSTANDING