Chapter 33. Tree Traversal

Tree traversal is the process of visiting the vertices of a tree in a specified order.

A tree has no natural linear order. Unlike an array, whose elements are visited from left to right, a tree branches. From a vertex, there may be several children or neighbors to visit next. A traversal rule resolves this choice.

Tree traversal is used to search trees, print their contents, evaluate expressions, copy structures, delete structures, compute summaries, and build auxiliary data. The common traversal families are depth-first traversal and breadth-first traversal. In rooted trees, these appear as preorder, postorder, inorder for binary trees, and level-order traversal.

33.1 Definition

Let

T=(V,E)

be a tree.

A traversal of $T$ is an ordered procedure that visits vertices of $T$ , usually exactly once.

The output of a traversal is a sequence

v_1,v_2,\ldots,v_n

containing the vertices of the tree in the order in which they are visited.

If the tree is rooted, the traversal usually begins at the root. If the tree is unrooted, one often chooses an arbitrary starting vertex and treats the tree as rooted at that vertex for the purpose of traversal.

33.2 Depth-First Traversal

Depth-first traversal explores as far as possible along one branch before returning to visit another branch.

In a rooted tree, this means that after entering a child subtree, the traversal continues inside that subtree before moving to the next sibling subtree. This behavior may be implemented recursively or by using an explicit stack.

Depth-first traversal is natural when the tree itself is recursively defined.

If a rooted tree has root $r$ and child subtrees

T_1,T_2,\ldots,T_k,

then a depth-first traversal processes these subtrees one at a time.

There are two standard depth-first orders for arbitrary rooted trees:

Traversal	Rule
Preorder	Visit the root before its subtrees
Postorder	Visit the root after its subtrees

For binary trees, there is also inorder traversal, because each vertex has a left subtree and a right subtree.

33.3 Preorder Traversal

Preorder traversal visits a vertex before visiting its children.

For a rooted tree:

Visit the root.
Traverse each child subtree in order.

If the root has child subtrees

T_1,T_2,\ldots,T_k,

then preorder has the form

r,\ \operatorname{preorder}(T_1),\ \operatorname{preorder}(T_2),\ldots,\operatorname{preorder}(T_k).

For a binary tree with root $r$ , left subtree $L$ , and right subtree $R$ , preorder is

r,\ L,\ R.

This is often called root-left-right order.

Example

Consider the rooted tree:

A(B(D,E),C(F)).

Here $A$ is the root. Its children are $B$ and $C$ . The children of $B$ are $D$ and $E$ . The child of $C$ is $F$ .

The preorder traversal is

A,B,D,E,C,F.

Preorder is useful when a parent must be processed before its descendants. For example, it can be used to copy a tree, serialize a hierarchy, or produce prefix notation from an expression tree.

33.4 Postorder Traversal

Postorder traversal visits a vertex after visiting its children.

For a rooted tree:

Traverse each child subtree in order.
Visit the root.

If the root has child subtrees

T_1,T_2,\ldots,T_k,

then postorder has the form

\operatorname{postorder}(T_1),\ \operatorname{postorder}(T_2),\ldots,\operatorname{postorder}(T_k),\ r.

For a binary tree with root $r$ , left subtree $L$ , and right subtree $R$ , postorder is

L,\ R,\ r.

This is often called left-right-root order.

Example

For the same rooted tree

A(B(D,E),C(F)),

the postorder traversal is

D,E,B,F,C,A.

Postorder is useful when a vertex depends on information from its descendants. It is used for deleting trees, computing subtree sizes, evaluating expression trees, and dynamic programming on trees.

33.5 Inorder Traversal

Inorder traversal is primarily defined for binary trees.

For a binary tree with root $r$ , left subtree $L$ , and right subtree $R$ , inorder traversal is

L,\ r,\ R.

That is:

Traverse the left subtree.
Visit the root.
Traverse the right subtree.

Example

Consider the binary tree

A(B(D,E),C(\varnothing,F)).

The inorder traversal is

D,B,E,A,C,F.

Inorder traversal is especially important for binary search trees. If each node key is greater than every key in its left subtree and less than every key in its right subtree, then inorder traversal visits the keys in ascending order.

33.6 Level-Order Traversal

Level-order traversal visits vertices by increasing depth.

It begins at the root, then visits all vertices at depth $1$ , then all vertices at depth $2$ , and so on.

This is the tree version of breadth-first search. It is commonly implemented with a queue.

For the rooted tree

A(B(D,E),C(F)),

the levels are:

Level	Vertices
$0$	$A$
$1$	$B,C$
$2$	$D,E,F$

Thus the level-order traversal is

A,B,C,D,E,F.

Level-order traversal is useful when the distance from the root matters. It appears in shortest-path trees, breadth-first search trees, heap storage, and layer-by-layer processing.

33.7 Recursive Traversal

Recursive traversal uses the recursive definition of a rooted tree.

For preorder:

\operatorname{Preorder}(T):

If $T$ is empty, stop.
Visit the root.
Apply preorder to each child subtree.

For postorder:

\operatorname{Postorder}(T):

If $T$ is empty, stop.
Apply postorder to each child subtree.
Visit the root.

For binary inorder:

\operatorname{Inorder}(T):

If $T$ is empty, stop.
Apply inorder to the left subtree.
Visit the root.
Apply inorder to the right subtree.

The recursion ends at leaves. A leaf has no child subtrees, so it is visited directly.

33.8 Stack-Based Traversal

Depth-first traversal can also be implemented with an explicit stack.

A stack is a last-in, first-out structure. It records vertices whose remaining work has been deferred.

For preorder traversal of an ordered rooted tree:

Push the root on the stack.
While the stack is nonempty:
- Pop a vertex.
- Visit it.
- Push its children in reverse order.

The reverse push order ensures that the leftmost or first child is processed first.

For binary trees, preorder can be written as:

preorder(root):
    if root is null:
        return

    stack = empty stack
    push root onto stack

    while stack is not empty:
        v = pop stack
        visit v

        if right(v) is not null:
            push right(v)

        if left(v) is not null:
            push left(v)

The stack version avoids recursive calls. It is useful when recursion depth may be large.

33.9 Queue-Based Traversal

Breadth-first traversal uses a queue.

A queue is a first-in, first-out structure. It stores vertices in the order in which they were discovered.

For level-order traversal:

level_order(root):
    if root is null:
        return

    queue = empty queue
    enqueue root

    while queue is not empty:
        v = dequeue queue
        visit v

        for each child c of v, in order:
            enqueue c

This algorithm visits vertices in increasing depth. All vertices at depth $d$ are processed before any vertex at depth $d+1$ .

33.10 Traversal and Running Time

Every standard traversal visits each vertex once.

If the tree has

n

vertices, then preorder, postorder, inorder, and level-order traversal all run in

O(n)

time.

The auxiliary memory depends on the traversal and the tree shape.

Traversal	Auxiliary structure	Typical extra space
Recursive DFS	Call stack	$O(h)$
Iterative DFS	Explicit stack	$O(h)$ to $O(n)$
BFS	Queue	$O(w)$

Here $h$ is the height of the tree, and $w$ is the maximum number of vertices on any level.

In a balanced binary tree,

h = O(\log n).

In a path-like tree,

h = O(n).

For breadth-first traversal, the queue may become large when the tree is wide.

33.11 Traversal of Binary Search Trees

Traversal order has special meaning in binary search trees.

Let $T$ be a binary search tree. For every vertex with key $k$ , all keys in the left subtree are less than $k$ , and all keys in the right subtree are greater than $k$ .

Then inorder traversal returns the keys in ascending order.

Theorem 33.1

The inorder traversal of a binary search tree lists its keys in increasing order.

Proof

We prove the statement by induction on the number of vertices.

If the tree is empty or has one vertex, the result is immediate.

Let the root have key $k$ . By the binary search tree property, every key in the left subtree is less than $k$ , and every key in the right subtree is greater than $k$ .

By the induction hypothesis, inorder traversal lists the left subtree in increasing order and the right subtree in increasing order.

Inorder traversal visits:

\text{left subtree},\quad k,\quad \text{right subtree}.

Therefore all listed keys appear in increasing order.

33.12 Traversal and Expression Trees

Expression trees use leaves for operands and internal vertices for operators.

For a binary expression tree:

Traversal	Notation produced
Preorder	Prefix notation
Inorder	Infix notation
Postorder	Postfix notation

For example, consider the expression tree for

(a+b)(c-d).

Its root is multiplication. The left subtree is addition, and the right subtree is subtraction.

Preorder gives

\ +\ a\ b\ -\ c\ d. $$

Inorder gives

(a+b)*(c-d).

Postorder gives

a\ b\ +\ c\ d\ -\ *.

Postorder is useful for evaluation because each operator is visited after its operands.

33.13 Computing Subtree Quantities

Postorder traversal is the standard method for computing quantities that depend on children.

For example, the size of the subtree rooted at $v$ is

\operatorname{size}(v) = 1+\sum_{c}\operatorname{size}(c),

where the sum is over all children $c$ of $v$ .

To compute this value, one must first compute the size of each child subtree. Therefore the natural traversal is postorder.

Similarly, postorder is used for:

Quantity	Recurrence
Height	$1+\max_c \operatorname{height}(c)$
Subtree size	$1+\sum_c \operatorname{size}(c)$
Leaf count	Sum of leaf counts of children
Dynamic programming value	Function of child values

The common pattern is that the value at a vertex is computed after the values of its children are known.

33.14 Traversal and Search

Traversal can be used to search for a vertex satisfying a condition.

For example, one may search for a key, a label, a minimum value, or a vertex with a certain property.

A generic depth-first search on a rooted tree has the form:

search(v):
    if v satisfies the condition:
        return v

    for each child c of v:
        result = search(c)
        if result is not null:
            return result

    return null

This is preorder search. It tests a vertex before searching below it.

Breadth-first search instead tests vertices level by level. It finds a satisfying vertex of minimum depth if one exists.

33.15 Traversal Orders and Reconstruction

Traversal sequences can sometimes determine a tree.

For binary trees with distinct labels:

Given traversals	Determines tree?
Preorder and inorder	Yes
Postorder and inorder	Yes
Preorder and postorder	Not always
Level-order and inorder	Yes

Inorder provides the division between left and right subtrees. Preorder identifies the root first. Postorder identifies the root last. Together with inorder, either is enough to reconstruct the tree.

Without inorder, the left-right division may remain ambiguous.

33.16 Traversal in General Trees

For a general rooted tree, a vertex may have any number of children.

Preorder and postorder remain natural:

\operatorname{preorder}(v): \quad v,\ T_1,\ldots,T_k.

\operatorname{postorder}(v): \quad T_1,\ldots,T_k,\ v.

Inorder has no single standard definition for general rooted trees, because there is no distinguished position between exactly two subtrees. Some conventions place the root after the first child subtree, but this is less universal than binary-tree inorder.

Thus inorder is best regarded as a binary-tree traversal.

33.17 Traversal in Algorithms

Tree traversal is a basic component inside larger algorithms.

Algorithmic task	Common traversal
Copy a tree	Preorder
Delete a tree	Postorder
Evaluate expression tree	Postorder
Print binary search tree in sorted order	Inorder
Compute tree height	Postorder
Find shallowest target	Level order
Serialize hierarchy	Preorder or level order
Dynamic programming on trees	Postorder

The traversal is chosen according to dependency. If a parent must be seen first, use preorder. If children must be computed first, use postorder. If depth matters, use level order.

33.18 Summary

Tree traversal converts a branching structure into an ordered sequence of vertex visits.

Depth-first traversal explores one branch before moving to another. Its main rooted forms are preorder and postorder. In binary trees, inorder traversal is also fundamental.

Breadth-first traversal visits vertices level by level and is implemented with a queue.

Each standard traversal visits all vertices in linear time. The appropriate traversal depends on the task: preorder for parent-first work, postorder for child-first computation, inorder for sorted output in binary search trees, and level order for depth-based processing.