Traversals

A list has one natural order: front to back. A tree has several. Visiting every node once, in some fixed order, is called a traversal. The four common orders each suit different jobs.

Pre-order, in-order, post-order

The first three orders all go deep first: they finish one subtree completely before starting the other. They differ only in when the node itself is visited, compared with its two subtrees:

• Pre-order: the node, then the left subtree, then the right subtree.
• In-order: the left subtree, then the node, then the right subtree.
• Post-order: the left subtree, then the right subtree, then the node.

Step through each order on the same tree:

In code, the three orders are the same function with the visit in a different place:

def preorder(node, out):
    if node is None:
        return
    out.append(node.value)        # before the subtrees
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)        # between them
    inorder(node.right, out)

def postorder(node, out):
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.value)        # after them

Each order has typical uses:

• Pre-order handles a node before its children: copying a tree, or writing it out so it can be rebuilt (lesson 7).
• In-order on a search tree gives the keys in sorted order (lesson 4).
• Post-order handles a node after its children: computing heights or sizes, freeing a tree, or adding up the sizes of folders, where each folder’s size needs its contents first.

Level order with a queue

The fourth order goes across instead of down: level 0, then level 1, then level 2, each from left to right. It is also called breadth-first. A queue (STAQ-3) does the work. Take a node from the front, visit it, and add its children to the back. Children always join behind every node of the current level, so levels come out in order.

from collections import deque

def level_order(root):
    out = []
    q = deque([root] if root is not None else [])
    while q:
        node = q.popleft()
        out.append(node.value)
        if node.left is not None:
            q.append(node.left)
        if node.right is not None:
            q.append(node.right)
    return out

To split the output into one list per level, take exactly len(q) nodes in each round, counted before the round starts. At that moment the queue holds exactly one level. Practice TREE-P1 asks for this.

Without recursion

The recursive versions go h + 1 calls deep, so a path-shaped tree with thousands of levels breaks them (lesson 1). Any recursion can be replaced by a stack you keep yourself (RECR-6). Pre-order is the easiest. Push the right child before the left, so that the left comes off the stack first:

def preorder(root):
    out, stack = [], [root] if root is not None else []
    while stack:
        node = stack.pop()
        out.append(node.value)
        if node.right is not None:
            stack.append(node.right)   # pushed first, used later
        if node.left is not None:
            stack.append(node.left)
    return out

In-order needs more care, because a node is visited only after its whole left subtree. Walk left as far as possible, pushing every node on the way. Then pop one, visit it, and move to its right child to start again:

def inorder(root):
    out, stack, cur = [], [], root
    while stack or cur is not None:
        while cur is not None:         # go left, remembering the way back
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()              # its left subtree is done
        out.append(cur.value)
        cur = cur.right                # now do its right subtree
    return out

A post-order without recursion can be made from the pre-order trick: visit node, right, left (push left first), then reverse the output. That gives left, right, node.

Cost and when to use which

Every traversal visits each node once and follows each edge a fixed number of times, so all four take O(n) time. Their extra space differs:

So the two families are good at opposite shapes: going deep is cheap on a bushy tree with short paths, and going across is cheap on a narrow, deep tree. Choose by the job first (does it need levels, or children before parents?), and by the shape second.