Visiting Every Node: Traversals

Four orders

“Traversing” a tree means visiting every node once. The three depth-first orders differ only in when you visit the node itself:

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

root = Node(1, Node(2, Node(4), Node(5)), Node(3))

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

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

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

print("pre: ", preorder(root))
print("in:  ", inorder(root))
print("post:", postorder(root))

Output

pre:  [1, 2, 4, 5, 3]
in:   [4, 2, 5, 1, 3]
post: [4, 5, 2, 3, 1]

Level order uses a queue

To go row by row, use a queue: take a node from the front, then add its children to the back. This is breadth-first search (BFS):

from collections import deque

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

root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))

q = deque([root])
level = 0
while q:
    row = []
    for _ in range(len(q)):          # everything in the queue now is one row
        node = q.popleft()
        row.append(node.value)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print("level", level, ":", row)
    level += 1

Output

level 0 : [1]
level 1 : [2, 3]
level 2 : [4, 5, 6]

Think of it like this: Preorder is like reading a book's table of contents: the chapter title first, then its sections. Postorder is like deleting a folder: you must delete everything inside it first.