Binary Tree Traversals

Four ways to visit a tree

A traversal visits every node of a tree exactly once. For a binary tree there are four standard orders:

        A
      /   \
     B     C
    / \     \
   D   E     F
      / \   /
     G   H I

The first three are depth-first: they go all the way down one branch before backing up. Level-order is breadth-first, like BFS on a graph.

One walk, three orders

The three depth-first orders are the same recursive walk:

def walk(node):
    if node is None: return
    # 1. pre-order visit
    walk(node.left)
    # 2. in-order visit
    walk(node.right)
    # 3. post-order visit

Picture walking around the outside of the tree with your left hand on it (an Euler tour). You pass every node three times: on its left side on the way down, underneath it between its two subtrees, and on its right side on the way back up. Writing the node down at the first, second or third pass gives pre-, in- or post-order. Choose All three at once in the 3D model to see the walker fill all three rows in a single walk.

A shortcut for exams: pre-order lists every node before any of its descendants, post-order lists it after all of them, and in-order places it between its left and right descendants.

Level-order needs a queue

Level-order cannot be written with this recursion. It uses a queue:

queue ← [root]
while queue is not empty:
    node ← queue.pop_front()
    visit(node)
    queue.push_back(node.left, node.right)     # if they exist

What each order is good for

Expression trees

An arithmetic expression is a tree: operators are internal nodes, numbers are leaves. For (3 + 4) × (8 − 6 / 2):

Postfix needs no brackets and is evaluated with a stack: push numbers; for an operator, pop two values and push the result. 3 4 + → 7; 8 6 2 / − → 5; 7 5 × → 35. Compilers and old HP calculators work exactly like this.

Rebuilding a tree from traversals

Pre-order and in-order together determine a binary tree uniquely (if the values are distinct). The first pre-order value is the root; find it in the in-order list, and everything to its left is the left subtree. Post-order plus in-order works the same way. Pre-order plus post-order alone is not enough in general.

Code

from collections import deque

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

def preorder(n):     # root, left, right
    return [n.val] + preorder(n.left) + preorder(n.right) if n else []

def inorder(n):      # left, root, right
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

def postorder(n):    # left, right, root
    return postorder(n.left) + postorder(n.right) + [n.val] if n else []

def level_order(root):
    out, queue = [], deque([root])
    while queue:
        n = queue.popleft()
        out.append(n.val)
        queue.extend(c for c in (n.left, n.right) if c)
    return out

def inorder_iterative(root):
    """In-order with an explicit stack instead of recursion."""
    out, stack, n = [], [], root
    while stack or n:
        while n:                    # go as far left as possible
            stack.append(n)
            n = n.left
        n = stack.pop()             # visit
        out.append(n.val)
        n = n.right                 # then the right subtree
    return out

def euler_tour(n, events):
    """One walk around the tree touches every node three times: before, between and after its subtrees."""
    if not n:
        return
    events.append(('pre', n.val))
    euler_tour(n.left, events)
    events.append(('in', n.val))
    euler_tour(n.right, events)
    events.append(('post', n.val))

def eval_postfix(tokens):
    stack = []
    for t in tokens:
        if t in '+-*/':
            b, a = stack.pop(), stack.pop()
            stack.append({'+': a + b, '-': a - b, '*': a * b, '/': a / b}[t])
        else:
            stack.append(float(t))
    return stack[0]

tree = Node('A', Node('B', Node('D'), Node('E', Node('G'), Node('H'))), Node('C', None, Node('F', Node('I'))))
print('pre  ', ' '.join(preorder(tree)))
# pre   A B D E G H C F I
print('in   ', ' '.join(inorder(tree)), '| iterative:', ' '.join(inorder_iterative(tree)))
# in    D B G E H A C I F | iterative: D B G E H A C I F
print('post ', ' '.join(postorder(tree)))
# post  D G H E B I F C A
print('level', ' '.join(level_order(tree)))
# level A B C D E F G H I
ev = []
euler_tour(tree, ev)
print('euler', ' '.join(f'{k}:{v}' for k, v in ev[:6]), '...')
# euler pre:A pre:B pre:D in:D post:D in:B ...

# (3 + 4) * (8 - 6 / 2) as an expression tree
expr = Node('*', Node('+', Node('3'), Node('4')), Node('-', Node('8'), Node('/', Node('6'), Node('2'))))
print('prefix ', ' '.join(preorder(expr)))
# prefix  * + 3 4 - 8 / 6 2
print('infix  ', ' '.join(inorder(expr)))
# infix   3 + 4 * 8 - 6 / 2
print('postfix', ' '.join(postorder(expr)), '=', eval_postfix(postorder(expr)))
# postfix 3 4 + 8 6 2 / - * = 35.0

Common mistakes

• Forgetting a whole subtree. In pre-order, after B comes all of B’s subtree (D, E, G, H) before C.
• Treating a missing child as nothing to do. C has no left child, so in-order goes C, then its right subtree (I, F).
• Using a stack for level-order. That gives a depth-first order; level-order needs a queue.
• Expecting in-order to be sorted on any tree. Only on a binary search tree.
• Reading infix from an expression tree without brackets. The tree knows the structure; plain in-order output loses it.