7.2.3 Three Preorder Traversals of a Binary Tree

Writing a recursive function to traverse a binary tree based on the recursive definition for preorder traversal is straightforward. The same is true for an inorder and postorder traversal.

Recursive Version

preorder(ptree)

/* Preorder traverses the

binary tree tree.

*/

binarytreepointer *ptree;

{

binarytreepointer 1,r,setnull(),left(),right();

if(*ptree != setnull())

{

>Comment

process(ptree);

>Comment

1 = left(*ptree);

>Comment

preorder(&l);

r = right(*ptree);

preorder(&r);

}

}

To convince yourself it works, simulate it on the tree of Figure 7.6(b).

Figure 7.7 Trees for (a) a Table of Contents, (b) an Arithmetic Expression, and (c) Components of a Program. Order of Access to Nodes is (d) for Preorder Traversal of (a), (e) for Inorder Traversal of (b), and (f) for Postorder Traversal of (c)

We will now develop an iterative procedure for contrast with the recursive one. It will also be useful if the programming language you are using is not recursive. Recall that the application of the definition of preorder traversal to Figure 7.6(b) required keeping track of the left subtree about to be traversed and remembering at which node to resume when that left subtree traversal terminated. For example, in Figure 7.6(b), after node L is processed, its left subtree must be preorder traversed. We must remember, after that traversal is complete, to resume the traversal by traversing L's right subtree. Put another way, it was necessary to suspend the current traversal, incurring its completion as a postponed obligation, and begin a traversal of the proper left subtree. These postponed obligations must be recalled and resumed in reverse order to the order in which they were incurred. That is, in a last-in first-out fashion. Obviously, the ubiquitous stack is called for. It seems to pop up everywhere.

To accomplish this let p point to the root of the subtree about to be traversed. After the processing of node.p, a pointer to its right subtree can be pushed onto the stack before traversal of its left subtree. At the time that node.p's right subtree is to be processed (when its left subtree traversal terminates), the stack will contain pointers to all right subtrees whose traversals have been postponed (right subtrees of nodes already accessed), but the top stack entry will point to node.p's right subtree. Thus popping the stack and setting p to the popped value correctly updates p to point to the correct next record to be accessed.

Nonrecursive Version Saving Right Pointers on a Stack

preorder(ptree)

/* Preorder traverses the

binary tree tree.

*/

binarytreepointer *ptree;

{

binarytreepointer p, null, setnull(), left(), right();

>Comment

stack s;

>Comment

null = setnull();

>Comment

setstack(&s);

>Comment

p = *ptree;

>Comment

while ((p != null) || !empty(&s))

>Comment

if (p != null)

{

>Comment

process (ptree,p);

>Comment

push (right(p),&s);

>Comment

p = left(p);

}

>Comment

else

>Comment

pop (&s,&p);

}

The while loop condition is true whenever the traversal is not yet completed. A nonnull p means that a record is pointed to by p and is the next one to be accessed and processed. A null p value means no record is pointed to by p, and some left subtree traversal must have just been completed. If, at that point, the stack is not empty, then more needs to be done; but if it is empty, then no right subtrees remain to be traversed, and the traversal is done. Again, to convince yourself the program works, simulate it on the tree of Figure 7.6(b).

The recursive procedure reflects the structure of binary trees and emphasizes that they are made up of a root with binary trees as subtrees. It sees the special cases, such as a null tree, and the substructures of the recursive definition, such as left and right subtrees. In order to develop the nonrecursive version, it is necessary to think of the binary tree as a collection of individual records. Writing the function then involves providing for the correct next record to be accessed and processed within the while loop. This is a general strategy for attempting to find nonrecursive solutions. The nonrecursive version requires that the structure be viewed as a collection of its individual parts, with each part treated appropriately and in the correct order. This explains why recursive versions are clearer.

An alternative nonrecursive function is based on saving on a stack the path from the root to the predecessor of the node currently being processed. It is useful if the processing of a node requires accessing its predecessor node. This alternative approach guarantees that at the time the node is processed its predecessor is at the top of the stack. However, this algorithm requires some searching to find the proper right subtree to traverse next when a subtree traversal has terminated. Such a termination is indicated by p being null. Figure 7.8 shows a situation when such a termination has occurred. P is null, having been set to the null right pointer value of node 10 after node 10's left subtree has been traversed. Looking back along the path from node 10 to the root, we find the path nodes 8, 6, 5, 1. It is not difficult to see that node 5's right subtree is where the traversal must resume. Precisely this path back toward the root must be followed until a node on this return path (node 6) is the left successor of its predecessor. P must then be set to the right subtree of that node (node 12) and the traversal resumed. If no node which is the left successor of its predecessor is found on the return path, the entire tree has been traversed.

Figure 7.8 Node 5's Left Subtree Has Just Been Traversed

The following function is a nonrecursive preorder traversal that saves the path to the root on a stack. Item returns a copy of the pointer at the top of the stack without disturbing the stack.

Nonrecursive Version Saving the Path to the Root on a Stack

preorder(ptree)

/* Preorder traverses the

binary tree tree.

*/

binarytreepointer *ptree;

{

binarytreepointer null,p,q,rightpointer;

binarytreepointer setnull(),left(),right(),item();

>Comment

stack s;

>Comment

null = setnull();

>Comment

setstack(&s);

>Comment

p = *ptree;

>Comment

while((p != null) || !empty(&s))

if(p != null)

1 if there is a current node

{

>Comment

process(ptree,p);

>Comment

if(left(p) != null)

{

>Comment

push(p,&s);

>Comment

p = left(p);

}

>Comment

else

{

>Comment

push(p,&s);

>Comment

p = right(p);

}

}

else

1 otherwise

{

>Comment

do

{

>Comment

pop(&s,&q);

>Comment

if (!empty(&s))

>Comment

rightpointer = right(item(&s));

>Comment

else

>Comment

rightpointer = null;

>Comment

}while(!empty(&s)&&(q==rightpointer));

>Comment

if(q != rightpointer)

>Comment

p = rightpointer;

}

}

Notice that the first two versions of the preorder traversal do not retain information about the depth of a node or about a node's predecessor, although they could be modified to do so. The third version retains this information, since the depth of the current node is equal to the number of stack entries plus one, and the top stack entry always points to the current node's predecessor. When this information is needed, the last version provides it directly, especially if a basic stack operation that returns the size of the stack is available.

Each of the three traversal functions can be modified to be a partial traversal when required, by including a variable done to signal termination, just as was done for the list traversals. This would be the case, for example, if you were traversing only to find a desired record. Similar function can be written for the inorder and postorder traversals.