Level Order Traversal

We mentioned in the previous lesson that visiting the nodes of a tree level-by-level, top to bottom is known as a level-order traversal. However, we haven't yet talked about how a level-order traversal is implemented.

Pre-order, in-order, and post-order traversals have a natural recursive implementation. A level-order traversal is actually easier to implement iteratively, but we will also need the help of queue to do it!

Implementing a level-order traversal

The basic idea behind a level-order traversal is that we want to visit all of the nodes at level h before we visit the nodes at level h + 1. To do so, we can enqueue the children of each node as we encounter them:

from collections import deque

def levelorder_print(self):
    q = deque()
    q.append(self.root)

    while len(q) > 0:
        node = q.popleft()
        print(node.val)

        if node.left is not None:
            q.append(node.left)

        if node.right is not None:
            q.append(node.right)

Watch the following video to see how a level-order traversal works: