The Algorithm Design Manual Second Edition

Traversal in a Tree

Visiting all the nodes in a rooted binary tree proves to be an important component

of many algorithms. It is a special case of traversing all the nodes and edges in a

graph, which will be the foundation of Chapter

5

.

A prime application of tree traversal is listing the labels of the tree nodes.

Binary search trees make it easy to report the labels in sorted order. By definition,

all the keys smaller than the root must lie in the left subtree of the root, and all

keys bigger than the root in the right subtree. Thus, visiting the nodes recursively

in accord with such a policy produces an in-order traversal of the search tree:

void traverse_tree(tree *l)

{

if (l != NULL) {

traverse_tree(l->left);

process_item(l->item);

traverse_tree(l->right);

}

}

---

80

3 .

D A T A S T R U C T U R E S

Each item is processed once during the course of traversal, which runs in O(n)

time, where n denotes the number of nodes in the tree.

Alternate traversal orders come from changing the position of process item

relative to the traversals of the left and right subtrees. Processing the item first

yields a pre-order traversal, while processing it last gives a post-order traversal.

These make relatively little sense with search trees, but prove useful when the

rooted tree represents arithmetic or logical expressions.