10.2 Tree Traversals and Expression Trees

Section 10.1 described a tree's shape. An algorithm often needs to process every vertex: list folders, print an organization chart, evaluate a formula, or serialize data. “Visit every vertex” is not yet a complete instruction because the same tree permits many visit orders.

A traversal is a rule that visits every vertex exactly once in a defined order. This section develops three depth-first traversals and then uses them to read and evaluate expression trees.

Why child order matters

Traversal order requires an ordered rooted tree. Recall that an ordered tree gives the children of each vertex a left-to-right order. Consider this tree description:

$A$ is the root. $B$ is visited before $C$ whenever an algorithm processes children from left to right. At $B$, child $D$ comes before $E$. Because the tree is binary, $F$ being the right child of $C$ also matters for inorder traversal.

If child order were unspecified, both $B,C$ and $C,B$ would be legal. A deterministic traversal therefore needs both the tree and its child order.

Recursive thinking fits trees

Chapter 7 defined a recursive structure by smaller structures of the same kind. A rooted tree has exactly that form:

1. there is a root; 2. each child is the root of a smaller subtree.

A subtree rooted at $v$ contains $v$ and every descendant of $v$. Traversal algorithms process the root and recursively process its child subtrees. The difference among traversals is when the root is processed.

To visit a vertex means to perform the required action there—for example, print its label or add its value. Visiting does not mean merely passing through an edge.

Preorder: root before subtrees

Preorder traversal visits a vertex before visiting its child subtrees from left to right.

PREORDER(v)
    visit v
    for each child c of v, from left to right
        PREORDER(c)

The base case is a leaf: visit it, then stop because it has no child subtrees.

For the example tree:

The route begins at $A$, completes all of $B$'s subtree, and only then enters $C$'s subtree. Preorder is useful when a parent must be handled before its contents, such as writing a folder name before listing the files inside it.

Postorder: subtrees before root

Postorder traversal recursively visits all child subtrees from left to right, then visits the vertex itself.

POSTORDER(v)
    for each child c of v, from left to right
        POSTORDER(c)
    visit v

For the same tree:

Every child appears before its parent. Postorder is useful when a parent's result depends on completed child results—for example, measuring all files before calculating a folder's total size.

Inorder: between the two binary subtrees

Inorder traversal is defined specifically for a binary tree:

1. traverse the left subtree; 2. visit the root; 3. traverse the right subtree.

INORDER(v)
    if v has a left child
        INORDER(v.left)
    visit v
    if v has a right child
        INORDER(v.right)

For the example tree:

At $C$, there is no left child, so $C$ is visited before its right child $F$. Inorder is not naturally defined for a vertex with three or more ordered children because there is no unique “middle” position for the parent.

One visit per vertex

Each traversal visits every one of the $n$ vertices exactly once and examines each child edge a constant number of times. Its step count is therefore

Recursive calls must remember unfinished ancestors. At most one call per level is active, so the number of simultaneously active calls is proportional to the height $h$:

A balanced tree can have small height, while a chain-shaped tree has $h=n-1$. The traversal still visits $n$ vertices in both cases, but the chain requires a deeper recursive call sequence.

Choose preorder, postorder, or inorder and then predict the visit sequence by selecting vertices directly on the tree. Correct choices illuminate the active recursive route; a wrong choice exposes which subtree or parent must be completed first. An animation can replay the learner's final sequence.

Expression trees give formulas a structure

An arithmetic expression contains values and operators. An expression tree is a binary tree in which

• every leaf stores an operand, such as a number or variable;
• every internal vertex stores a binary operator, such as $+,-,\times,$ or $\div$;
• the left and right subtrees are the operator's left and right inputs.

Consider

Its root is $\times$. The root's left subtree represents $3+5$, and its right subtree represents $10-4$:

The tree records grouping without relying on precedence conventions. Swapping the children of subtraction changes $10-4$ into $4-10$, so left and right positions must be preserved.

Three traversals produce three notations

Applying the traversal orders to an expression tree produces familiar expression formats.

Infix notation

Inorder places each operator between its inputs. Parentheses must be restored to preserve subtree boundaries:

This is infix notation because each operator appears inside, or between, its operands.

Prefix notation

Preorder places each operator before its two operand subexpressions:

This is prefix notation. If every operator has a known number of inputs, parentheses are unnecessary because the tree can be reconstructed from the order.

Postfix notation

Postorder places each operator after its two operand subexpressions:

This is postfix notation. Again, fixed operator arity removes the need for parentheses.

Evaluating an expression tree

Evaluation follows the same dependency as postorder: calculate child values before applying the parent operator.

Define $\operatorname{eval}(v)$ recursively:

where $L$ and $R$ are the left and right children.

For the example, first evaluate the two lower subtrees:

Then evaluate the root:

The complete dependency pipeline is

Division adds an important boundary case: before computing $a\div b$, the algorithm must check that $b\ne0$. A valid tree shape can still represent an undefined arithmetic expression.

Build a two-level expression tree by assigning operators and leaf values. The forge updates fully parenthesized infix, prefix, postfix, and bottom-up evaluation simultaneously. Swapping subtrees makes the effect of operand order visible, while division by zero deliberately stops the evaluation pipeline.

Section checklist

• A traversal defines a reproducible one-visit order.
• Preorder visits a parent before its subtrees.
• Postorder visits subtrees before their parent.
• Inorder means left subtree, parent, right subtree and requires a binary tree.
• All three traversals take $\Theta(n)$ time for $n$ vertices.
• Expression-tree leaves are operands; internal vertices are operators.
• Preorder, inorder, and postorder produce prefix, infix, and postfix notation.
• Evaluation is bottom-up and must respect left and right operand positions.

We can now process a tree once it is given. Section 10.3 gives tree edges a new role: left and right branches become bits in a prefix code, while symbol frequencies determine which leaves should be shallow or deep.