Traversals: Visiting Every Node

Walking a tree

A list has one obvious visiting order, front to back. A tree does not, so the useful orders get names.

For binary trees, where each node has at most a left and a right child, three recursive orders differ only in when the node itself is handled.

• preorder takes the node, then the left subtree, then the right subtree.
• inorder takes the left subtree, then the node, then the right subtree.
• postorder takes the left subtree, then the right subtree, then the node.

Each has a job it is right for. Preorder copies a tree top-down, since a parent must exist before its children can attach to it. Postorder deletes one safely, since children must be gone before their parent, the same reason a folder's contents are removed before the folder. Inorder is the star of lesson 7-3.

All three dive as deep as possible before backing up, which makes them depth-first. The recursion itself is what remembers the way back, since each pending call sits on the call stack until its subtree finishes.

The fourth order, level-order, visits ring by ring instead, and the tool for it is already familiar: the BFS frontier queue from lesson 5-3.

The three depth-first orders

The six-node tree from the figure, walked three ways.

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

#        F
#      /   \
#     B     G
#    / \     \
#   A   D     I
root = Node("F")
root.left = Node("B")
root.right = Node("G")
root.left.left = Node("A")
root.left.right = Node("D")
root.right.right = Node("I")

def preorder(node, out):
    if node is None:
        return
    out.append(node.value)
    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)
    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)

for name, fn in [("pre", preorder), ("in", inorder), ("post", postorder)]:
    out = []
    fn(root, out)
    print(name, " ".join(out))

Output

pre F B A D G I
in A B D F G I
post A D B I G F

The three functions are identical except for the line that out.append sits on. Moving one statement is the entire difference between the orders, which is worth pausing on, because the names sound like three separate algorithms.

if node is None: return is the base case that makes the recursion safe. A missing child is a valid input, so the caller never has to check before recursing, and G's absent left child is handled by that line alone.

The outputs are worth reading against the tree. Preorder starts at the root F, inorder starts at the leftmost node A, and postorder ends at the root, which is exactly the property the delete case needs.

Level-order with a queue

The BFS pattern from lesson 5-3, with tree children in place of friends.

from collections import deque

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

root = Node("F")
root.left = Node("B")
root.right = Node("G")
root.left.left = Node("A")
root.left.right = Node("D")
root.right.right = Node("I")

def level_order(root):
    out = []
    frontier = deque([root])
    while frontier:
        node = frontier.popleft()
        out.append(node.value)
        if node.left:
            frontier.append(node.left)
        if node.right:
            frontier.append(node.right)
    return out

print(" ".join(level_order(root)))

Output

F B G A D I

This is lesson 5-3's frontier loop with almost nothing changed. Dequeue a node, record it, and enqueue whatever it leads to, guarding each child with if node.left: so a missing child is skipped.

One thing the friend-network version needed is missing here, and its absence is the point. There is no seen set, because a tree has no cycles, so no node can be reached twice.

The output is ring by ring: F at depth 0, then B G at depth 1, then A D I at depth 2. FIFO is what enforces that, exactly as it enforced the introduction rounds.

This traversal is iterative rather than recursive, and that difference is structural. Depth-first orders let the call stack hold the pending work, while level-order needs a queue, and a queue cannot be simulated by recursion.

Deleting a folder tree calls for postorder.

Postorder handles the node last, only after both of its subtrees are fully processed, so every child is already gone by the time its parent is removed. That is the exact requirement, and no other order satisfies it.

The alternatives fail in instructive ways. Preorder removes the parent first, which would strand the children as unreachable nodes with nothing pointing at them. Level-order goes top-down by depth, which has the same problem one level at a time.

Turning it around gives the general rule. Preorder is right when a node must be handled before whatever depends on it, as in copying, and postorder is right when a node must be handled after the things it contains, as in deleting, or summing sizes, or freeing memory.