# CHAPTER 7: TREES

Introduces three new data structures

binary trees

trees

ordered trees

Shows

how to apply them to store data

that they are useful as conceptual aids to problem solving and uses them in the n-queens problem

how to implement them

Emphasizes the basic operations for

binary trees

preorder, inorder, and postorder traversals

trees

preorder and postorder traversals

backtracking

Clarifies the relation between recursion, trees, and stacks

Discusses recursive solutions to show

when they are efficient

how to improve them

# 7.1: Branching Out

All data structures provide a way to organize data. Different structures serve different purposes. Complex lists, as shown by the information retrieval case study of Chapter 6, can result in considerable intertwining and sharing of lists and data. Everyone is familiar with the concept of a family tree. In fact, a nice exercise would be to print the family tree for an individual whose family history is stored in the data base of that case study. The family tree is actually embedded within the lists containing the family history. Trees may be viewed as a special case of lists in which no intertwining or sharing takes place. They are the basis for structures and operations used in all aspects of programming, from the structure of programs for compilers, to work in data processing, information retrieval, and artificial intelligence. Trees are ubiquitous; they seem to sprout everywhere--even in the field of computer science!

Trees play a significant role in the organization of data for efficient information retrieval and are ideal candidates for fast searches, insertions, deletions, and sequential access. Efficiency and speed are possible because trees "spread out" the data they store, so that different paths in the tree lead quickly to the relevant data. They are also convenient for conceptualizing algorithms.

Many problems can be solved by imagining all the possible answers, represented as a tree. The algorithm or program is then viewed as a traversal through the tree. The general procedure for a traversal through a tree, which will be developed in this chapter, can then be adapted and used as the basis for the program. This often results in easily created and efficient programs. In such cases the tree itself serves as a conceptual aid and need not actually be "grown" or stored in memory. Nevertheless, it provides the framework for obtaining the algorithm.

#### Figure 7.1 Capturing Inclusion Relationships

The null binary tree, or

A root node and its left and right subtrees, which are themselves binary trees with no common nodes

This recursive definition emphasizes the fact that binary trees with at least one node are composed of a root and two other binary trees, called the left and right subtrees, respectively. These subtrees, in turn, have the same structure. All binary trees consist of nodes, except for the null binary tree, which has no nodes. The null binary tree, just like the null list, cannot be "drawn." Both are used to make definitions more uniform and easier, and both represent the smallest data structure of their kind. There is exactly one binary tree with one node, its root. This tree has null left and right subtrees. The two binary trees with exactly two nodes are pictured as in Figure 7.2. One has a root and a nonnull left subtree, the other a root and a nonnull right subtree. Figure 7.3 pictures a larger binary tree.

#### Figure 7.2 Two Two-Node Binary Trees

Notice that, starting from any node in the tree, there is exactly one path from the node back to the root. This path is traveled by following the sequence of predecessors of the original node until the root is reached. For node 18, the sequence of predecessors is 9, 4, 2, and 1. There is always exactly one path from the root to any node.

#### Figure 7.4 The Right Subtree of the Root of Figure 7.3

Suppose your program must count the number of occurrences of each integer appearing in an input sequence of integers known to be between zero and 100. This is easy. Store the count for each integer of the allowed range in an array and increment the appropriate entry by 1 for each integer as it is input. The code would be array [i] + +, where i is the variable containing the integer just read. Note that the efficiency of this solution derives from the selection operation for an entry, which is supported by the array data structure.

## 7.1.1 Depth versus Capacity*

*This section can be omitted on first reading.

`n  2d - 1`

The minimum possible depth, dmin, for a binary tree with n nodes will be given by

`dmin = lg (n + 1)`

where x indicates the smallest integer that equals or exceeds x. If n = 20, then dmin = lg 21 = 4.39 = 5; and if n = 31, then dmin = lg 32 =5. The binary tree corresponding to dmin may always be taken as a complete binary tree. Consequently, the depth of a complete binary tree will never exceed (lg n) + 1. This contrasts sharply with the depth of the sparsest binary tree with n nodes, which is n . For instance, if n is 1,000, the complete binary tree has a depth of only 10, while the sparsest has depth 1,000. This has important implications for how trees are constructed and for information retrieval, as shown in Chapter 9.

# 7.2: Trees of Records

Balanced trees and binary search trees (Chapter 9) and heaps (Chapter 8) are all binary trees with special properties that make them useful for storage of information. The properties that make them useful favor efficient searching, inserting, and deleting. Each of these types of binary tree requires its own algorithms for these operations, in order to take advantage of or to preserve their characteristics. For now, to get the flavor of these operations, consider some simple examples.

## 7.2.1 Insertion and Deletion of Records in Binary Trees

To accomplish an insertion, storage must first be allocated for a new record. Next, its fields must be set correctly; this includes entering data into the record and setting its pointers to the succeeding left and right nodes, or to null if it is a leaf. Finally the proper pointer adjustments must be made in the tree to the predecessor of the new entry. Consider Figure 7.6, which shows a binary tree t before and after the insertion of a new entry C, which replaces predecessor O's null right subtree. The information for the new record is assumed to reside in value, so C is stored in value. Thus the new record must have its information field set to value and its left and right pointer fields set to null. The predecessor's right pointer field must be set to point to the new record. This is accomplished by the following.

`p = avail();`

`setinfo(p,&value);`

`setleft(p,null);`

`setright(p,null);`

`setright(predecessor,p);`

#### Figure 7.6 A Binary Tree T before and after the Insertion of C

If a new record is to replace a nonnull subtree (say, if C were to replace U in t), then the new record's left and right pointer fields would have to be adjusted accordingly. The left and right pointers from U would have to be copied into the new record's (C's) pointer fields. Furthermore, the storage for the replaced record U might be reclaimable. If so, care is required to save the pointer to it in its predecessor's left or right field so that its storage can be reclaimed. In this example, after saving the pointer to U, the right pointer of U's predecessor, L, would be replaced by a pointer to C, its new right node. Then U's storage can be reclaimed. The code below does this correctly, assuming predecessor points to a record whose nonnull right subtree is to be replaced.

`q = right(predecessor);`

`p = avail();`

`setinfo(p,&value);`

`setleft(p,left(q));`

`setright(p,right(q));`

`setright(predecessor,p);`

`reclaim(q);`

Right returns a copy of the right pointer field value of the record pointed to by its parameter. This code is for illustrative purposes. If the record is really reclaimable, it would be more efficient simply to replace its info field by the new info value. The statement setinfo(q,&value) would suffice. However, if the replaced record were needed for another purpose, say for insertion in another binary tree, then this would not work.

The deletion of a terminal node pointed to by p, whose predecessor is pointed to by predecessor, may be accomplished by the following.

`if(left(predecessor) == p)`

`setleft(predecessor,null);`

`else`

`1 otherwise`

`setright(predecessor, null);`

`1 set its predecessor's right pointer to null`

The wary reader may have qualms about the code developed for insertion and deletion. Remember--special cases must always be checked. When insertion or deletion occurs at the root node, indicated by a null value in predecessor, it is the name of the tree whose pointer must be adjusted. The illustrative code fails in this case. You should modify the program segments so that they also account for this special case.

## 7.2.2 Climbing Binary Trees

Pre-, in-, and postorder traversals are often referred to mnemonically as root-left-right, left-root-right, and left-right-root traversals. The prefixes pre, in, and post refer to whether the root is accessed prior to, in between, or after the corresponding traversals of the left and right subtrees. In all cases, the left subtree is traversed before the right subtree. When nodes are listed in the order in which they are processed, all nodes in the left subtree appear before all nodes in the right subtree, no matter which traversal is used. However, the type of traversal determines where the root appears. Since we defined binary trees recursively, it is convenient to give recursive definitions for these traversals.

To preorder traverse a binary tree:

if the binary tree is not the null binary tree, then

1. access and process its root

2. traverse its left subtree in preorder

3. traverse its right subtree in preorder

To inorder traverse a binary tree:

if the binary tree is not the null binary tree, then

1. traverse its left subtree in inorder

2. access and process its root

3. traverse its right subtree in inorder

To postorder traverse a binary tree:

if the binary tree is not the null binary tree, then

1. traverse its left subtree in postorder

2. traverse its right subtree in postorder

3. access and process its root

Let's apply these definitions to Figure 7.6(b).

To do a preorder traversal of t, since it is not null, requires that its root, L, be accessed and processed first. Next, the left subtree of t must be preorder traversed. Applying the definition to it, its root, O, is accessed and processed. Since O's left subtree is null, its right subtree is traversed next in preorder. This results in C being accessed and processed, terminating the preorder traversal of O's right subtree and also of t's left subtree. Completing t's traversal requires a preorder traversal of its right subtree, resulting in U, S, and T being accessed and processed in turn.

An inorder traversal of t requires its left subtree to be inorder traversed first. Applying the definition to this left subtree requires its null left subtree to be inorder traversed (note how easy that is), its root O to be accessed and processed next, and then its right subtree to be inorder traversed, which results in C being accessed and processed. This terminates the inorder traversal of t's left subtree. T's root, L, must then be accessed and processed, followed by an inorder traversal of t's right subtree. This causes S, U, and T to be accessed and processed in turn, completing the inorder traversal of t.

Try applying the postorder traversal definition to t yourself. The sequences below represent the order in which the records stored at the nodes of t are accessed and processed for each of the traversals.

`locust`

`oclsut`

`costul`

Notice that the terminal nodes C, S, and T are dealt with in the same order for all three traversals. This is not just a coincidence but will always happen.

The trees of Figure 7.7 represent a table of contents, an arithmetic expression, and a program that invokes functions that, in turn, invoke other functions. Traversing these trees, respectively, in pre-, in-, and postorder results in the order of access to nodes shown in Figure 7.7(d-f). Each is a natural application of one of the three traversals: a listing of the table of contents, an arithmetic expression in the usual notation, and a listing of the order in which the functions are needed to test another function (for example, P1 and P2 are needed to test P3).

Not all data structures need to be traversed. For example, stacks, queues, heaps, and the hash tables to be introduced in Chapter 9 are not normally traversed. Just as applications of arrays and, even more so, lists often reduce to traversals, applications of binary trees often do as well. Therefore procedures for their traversal merit study.

## 7.2.3 Three Preorder Traversals of a Binary Tree

Recursive Version

`preorder(ptree)`

`/* Preorder traverses the`

`binary tree tree.`

`*/`

`binarytreepointer *ptree;`

`{`

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

`if(*ptree != setnull())`

`{`

`process(ptree);`

`1 = left(*ptree);`

`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.

`preorder(ptree)`

`/* Preorder traverses the`

`binary tree tree.`

`*/`

`binarytreepointer *ptree;`

`{`

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

`stack s;`

`null = setnull();`

`setstack(&s);`

`p = *ptree;`

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

`if (p != null)`

`{`

`process (ptree,p);`

`push (right(p),&s);`

`p = left(p);`

`}`

`else`

`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.

`preorder(ptree)`

`/* Preorder traverses the`

`binary tree tree.`

`*/`

`binarytreepointer *ptree;`

`{`

`binarytreepointer null,p,q,rightpointer;`

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

`stack s;`

`null = setnull();`

`setstack(&s);`

`p = *ptree;`

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

`if(p != null)`

`1 if there is a current node`

`{`

`process(ptree,p);`

`if(left(p) != null)`

`{`

`push(p,&s);`

`p = left(p);`

`}`

`else`

`{`

`push(p,&s);`

`p = right(p);`

`}`

`}`

`else`

`1 otherwise`

`{`

`do`

`{`

`pop(&s,&q);`

`if (!empty(&s))`

`rightpointer = right(item(&s));`

`else`

`rightpointer = null;`

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

`if(q != rightpointer)`

`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.

# 7.3: Using the Traverse Functions for Binary Trees

In this section a number of examples are presented to show how the traverse functions developed thus far can be applied to develop solutions to programming problems.

Print the number of terminal nodes in a binary tree tree.

The nonrecursive preorder traversal that saves right subtree pointers on a stack will be used to perform this task. The other versions could have been adapted as readily. The approach taken is to leave the traverse function as it is and write process to turn preorder into a solution to the problem.

To accomplish this, process must test each node it deals with to see if it is a terminal node. If so a counter, tncount, should be increased by 1. Making tncount a static variable in process allows its values to be preserved between calls to process. The first time process is called during the traversal it must initialize tncount to zero, and the last time it is called, in addition to updating tncount, process must print its final value.

`process(ptree,p,ps)`

`/* Prints the number of terminal nodes in`

`binary tree tree when p points to the last`

`node in a preorder traverse of tree which`

`saves right pointers on stack s.`

`*/`

`binarytreepointer *ptree,p;`

`stack *ps;`

`{`

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

`static int tncount;`

`null = setnull();`

`if(p == *ptree)`

`tncount = 0;`

`if((left(p) == null) && (right(p) == null))`

`{`

`tncount++;`

`if(last (ps))`

`printf("\n The number of terminal nodes is %d",tncount);`

`}`

`}`

In this case process will be written to make a solution out of the nonrecursive version of preorder that stores the path from the root to the node being processed. This is convenient, since the predecessor of the node to be processed is required by process when the insertion is made, and it will be the top stack entry at that time.

`process(ptree,p,null,ps,value)`

`/* If p points to the first terminal node, encountered`

`in a preorder traversal of binary tree tree that saves`

`the path to the root on stack s, then replaces that node by`

`a new node whose info field is set to the contents of value.`

`*/`

`binarytreepointer *ptree,p,null;`

`stack *ps;`

`int value;`

`{`

`binarytreepointer q,ptr,avail(),`

`left(),right();`

`if((left(p) == null)&&(right(p) == null)`

`{`

`ptr = avail();`

`setinfo(ptr,&value);`

`setleft(ptr,null);`

`setright(ptr,null);`

`if(p != *ptree)`

`{`

`q = item(ps);`

`if(left(q) == p)`

`setleft(q,ptr);`

`else`

`setright(q,ptr);`

`}`

`else`

`*ptree = ptr;`

`setstack(ps);`

`}`

`}`

When process is called, it tests whether the node is a terminal node. Since it will cause the traversal to be terminated after the replacement, this must be the first terminal node. Storage is then obtained for the new record and its fields filled in properly. Since it will be a terminal node, its pointer fields are set to null. To insert the new record, the predecessor of the terminal node must have one of its pointer fields set to point to the new record. The correct one is determined by whether the replaced record was its left or right successor. The special case of the insertion occurring at the root requires only that tree be set to point to the new record. Finally, setting the stack to empty ensures that the traversal will be aborted.

Value is passed by preorder to process. Item simply returns a copy of the top stack entry.

The nonrecursive version of preorder that saves the path to the root on the stack can be turned into such a function. When a node is being processed, its depth is one more than the number of stack entries at that moment. To determine the depth, initialize a variable d to 1 and size to zero before the while loop, increase size by 1 after push, and decrease it by 1 after pop. Give process access to d and size. Process must simply compare size+1 to d, and when greater, set d to size+1. After termination of the traversal, depth must return d.

Another solution for depth can be obtained by recursion. This requires a way to express the depth recursively. The depth of a binary tree t is

Zero if t is null, else

One more than the maximum of the depths of t's left and right subtrees

Now the function can be written directly as follows:

`depth(tree)`

`/* Returns the depth of `

`the binary tree tree.`

`*/`

`binarytreepointer tree;`

`{`

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

`if(tree == setnull())`

`return(0);`

`else`

`return(1 + max(depth(left(tree)),`

`depth(right(tree))));`

`}`

where max returns the maximum of its parameters as its value.

# 7.4: Implementing Binary Trees

1. Using an array of records with just an information field

2. Using records with an information field and left and right pointer fields linked together via their pointer fields

3. Using a list-structure

Chapter 8 contains an application of the first implementation. A program using the second implementation, with the records stored in dynamic memory, is included. The program specifies the details of this important representation and illustrates how to create and process binary trees and how to test functions developed in the earlier examples.

## 7.4.1 Sequential Representation

#### Figure 7.9 Sequential Representation of a Binary Tree

The sequential representation of a binary tree is obtained by storing the record corresponding to node i of the tree as the ith record in an array of records, as shown in Figure 7.9. A node not in the tree can be recognized by a special value in its corresponding array position (such as node 8, which has - as its value) or by a node number (like 24) that exceeds the highest node number in the tree (20 in this example). Given a pointer p to a node in the array, it is easy to determine the position of its predecessor (p/2), its left successor (2*p), and its right successor (2*p+1).

A binary tree with n nodes will require an array length between n and 2n - 1. The smallest length (n) is sufficient when the binary tree is complete, and the greatest length (2n - 1) corresponds to the case of an extremely skewed binary tree whose nodes have only right successors. No space in the array is unused for a complete binary tree, and the array length is proportional to the number of nodes in the tree. However, a sparse tree can waste a great deal of array space. The worst case requires 2n - 1 positions but uses only n. Thus the sequential representation is convenient for dealing with complete static binary trees. Such trees arise, for example, when you must put student records in alphabetical order by student name. How to do such ordering is considered in the next chapter (Section 8.4). For cases when the tree may change size or shape drastically, the sequential representation is not appropriate. An example of this situation is found in the integer or word counting problem of Section 7.1.

1. A left pointer field,

2. An information field

3. A right pointer field

(called here the leftptr, info, and rightptr fields). This is the most common representation. The left and right pointer fields link records of the tree, just as the link and sublist fields of lists link their records. In effect, the pointer fields specify a node's left and right subtrees, just as the sublist field of a list specifies its sublist. The leftptr and rightptr fields of a node point to the record that represents, respectively, the root of the node's left and right subtree. The info field contains the information stored at the node. A variable referred to as the name of the tree points to the record representing the root of the tree, and a null pointer in the name denotes the null tree.

We can store each record of a binary tree using an array of records as shown in Figure 7.10, just as was done for the records of lists. The binary tree fred, for example, has its root stored in position 5 of the array, while the root of t is in position 2. the left successor of fred's root is stored in position 8, and its right successor in position 0. A minus one is used as the null pointer.

#### Figure 7.10 Linked Representation for Binary Trees with Records Stored in an Array

The definitions for the records and the array declaration are as follows.

`typedef struct`

`{`

`whatever info;`

`int leftptr;`

`int rightptr;`

`}binarytreenode;`

`typedef int binarytreepointer;`

`# define MAX 50`

`typedef binarytreenode recordsarray[MAX];`

`recordsarray records;`

Instead of using an array and array indices, we may store the records of the tree in dynamic memory and use pointers. The record declarations then become

`typedef struct treenode`

`{`

`whatever info;`

`struct treenode *leftptr;`

`struct treenode *rightptr;`

`}binarytreenode,*binarytreepointer;`

Such linked representations require storage proportional to the number of nodes of the binary tree represented, no matter what the shape of the binary tree. Contrast this with the sequential representation of binary trees. If a linked representation uses three elements per record, whereas a sequential representation uses one element per record, then for complete binary trees three times as much storage is used in a linked representation as in a sequential one. If the binary tree is not complete, then the sequential representation may require storage proportional to 2d - 1, where d is the depth of the binary tree. This could result in significant amounts of wasted space; there may not even be enough storage. Consequently, the sequential representation is more practical only when dealing with complete or nonsparse binary trees.

Using the linked representation, it is obviously possible to insert or delete records, once we know where to do so, by making changes in only a few pointer fields.

The following program illustrates the binary tree implementation with records stored in dynamic memory. It is a program that could be used to test all the functions of Section 7.3 (although they have been renamed). The names are self-explanatory. The input consists of

An integer to indicate whether the binary tree being created is null,

A sequence of data for each record

A value for the info field of a new node

The sequence is assumed to be in the order in which the records are accessed in a preorder traversal of the binary tree being input. For example, if the input corresponded to the right subtree of Figure 7.9 and the new value replacing the first terminal node were 50, then the input would be as follows. (Program output and prompts are not shown.)

Typical Input

`1    indicates nonnull binary tree`

`3    data for the root;`

`11   both its subtrees are nonnull`

`6    data for the next record in preorder;`

`11   both its subtrees are nonnull1`

`12   data for the next record in preorder;`

`00   both its subtrees are null1`

`13   data for the next record in preorder;`

`00   both its subtrees are null`

`7    data for the next record in preorder;`

`00   both its subtrees are null`

`50   the new value`

The Program

`Reads the data for nodes of a binary tree, creates`

`the tree and prints how many terminal nodes it`

`has and its depth, reads the value for the new node,`

`replaces the first terminal node in preorder access`

`by the new node, and then prints all the final binary`

`tree's nodes, its terminal count, and its depth.`

`#include <stdio.h>`

`typedef struct treerecord`

`{`

`int info;`

`struct treerecord *leftptr;`

`struct treerecord *rightptr;`

`}binarytreerecord,*binarytreepointer;`

`#define NULL 0`

`binarytreepointer left(p)`

`/* Returns a copy of the left`

`pointer of the node p points to.`

`*/`

`binarytreepointer p;`

`{`

`return(p->leftptr);`

`}`

`binarytreepointer right(p)`

`/* Returns a copy of the right`

`pointer of the node p points to.`

`*/`

`binarytreepointer p;`

`{`

`return(p->rightptr);`

`}`

`binarytreepointer setnull()`

`/* Returns a null pointer */`

`{`

`return(NULL);`

`}`

`binarytreepointer avail()`

`/* Returns a pointer to storage`

`allocated for a new node.`

`*/`

`{`

`return(malloc(sizeof(binarytreerecord)));`

`}`

`setinfo(p,pvalue)`

`/* Copies the contents of value`

`into the record p points to.`

`*/`

`binarytreepointer p;`

`int *pvalue;`

`{`

`p->info = *pvalue;`

`}`

`setleft(p,q)`

`/* Copies q into the left pointer`

`of the record p points to.`

`*/`

`binarytreepointer p,q;`

`{`

`p->leftptr = q;`

`}`

`setright(p,q)`

`/* Copies q into the right pointer`

`of the record p points to.`

`*/`

`binarytreepointer p,q;`

`{`

`p->rightptr = q;`

`}`

`printnode(pl,ptr)`

`/* Prints the info field of the`

`record ptr points to.`

`*/`

`binarytreepointer *pl,ptr;`

`{`

`printf("\n %d",ptr->info);`

`}`

`main()`

`/* Reads the data for nodes of a binary tree, creates`

`the tree and prints how many terminal nodes it`

`has and its depth, reads the value for the new node,`

`replaces the first terminal node in preorder access`

`by the new node, and then prints all the final`

`binary tree's nodes, its terminal count, and its`

`depth.`

`*/`

`{`

`int n,value;`

`binarytreepointer t,setnull(),avail();`

`printf("\n enter binarytree 0 for null tree 1\`

`otherwise \n");`

`scanf("%d",&n);`

`if (n == 0)`

`t = setnull();`

`else`

`{`

`t = avail();`

`createtree(&t);`

`}`

`printtree(&t);`

`terminalcount(&t);`

`printf("\n The depth is %d",depth(t));`

`printf("\n enter value ");`

`scanf("%d",&value);`

`replacefirstterminal(&t,value);`

`printtree(&t);`

`terminalcount(&t);`

`printf("\n The depth is %d",depth(t));`

`}`

`createtree(ptree)`

`/* Read the data and create the binary tree tree. */`

`binarytreepointer *ptree;`

`{`

`binarytreepointer l,r,setnull(),left(),right();`

`if (*ptree != setnull())`

`{`

`createnode(ptree);`

`l = left(*ptree);`

`createtree(&l);`

`r = right(*ptree);`

`createtree(&r);`

`}`

`}`

`createnode(pptr)`

`/* Reads the data, and fills in the fields`

`of the node pointed to by ptr.`

`*/`

`binarytreepointer *pptr;`

`{`

`int leftlink,rightlink,value;`

`binarytreepointer setnull(),avail();`

`printf("\n enter info \n");`

`scanf("%d",&value);`

`setinfo(*pptr,&value);`

`printf("\n enter enter left & right ptrs \n");`

`scanf("%d %d",&leftlink,&rightlink);`

`if (leftlink == 0)`

`setleft(*pptr,setnull());`

`else`

`setleft(*pptr,avail());`

`if (rightlink == 0)`

`setright(*pptr,setnull();`

`else`

`setright(*pptr,avail());`

`}`

`#define LIMIT 50`

`typedef binarytreepointer whatever;`

`typedef struct`

`{`

`whatever stackarray[LIMIT];`

`int top;`

`}stack;`

`#define TRUE 1`

`#define FALSE 0`

`setstack(ps)`

`/* Sets the stack s to empty. */`

`stack *ps;`

`{`

`(*ps).top = -1;`

`}`

`empty(ps)`

`/* Returns true only if stack s is empty.*/`

`stack *ps;`

`{`

`return((*ps).top == -1);`

`}`

`push(value,ps)`

`/* Inserts value at the top of stack s. */`

`whatever value;`

`stack *ps;`

`{`

`if ((*ps).top == (LIMIT - 1))`

`overflow(ps);`

`else`

`{`

`(*ps).top = (*ps).top + 1;`

`(*ps).stackarray[(*ps).top] = value;`

`}`

`}`

`pop(ps,pvalue)`

`/* Removes the top entry of stack s`

`and copies its contents into value.`

`*/`

`stack *ps;`

`whatever *pvalue;`

`{`

`if (empty(ps))`

`underflow(ps);`

`else`

`{`

`*pvalue = (*ps).stackarray[(*ps).top];`

`(*ps).top = (*ps).top - 1;`

`}`

`}`

`whatever item(ps)`

`/* Returns a copy of the top entry on stack s. */`

`stack *ps;`

`{`

`return((*ps).stackarray[(*ps).top]);`

`}`

`last(ps)`

`/* Returns true only if stack s`

`contains no non null pointers.`

`*/`

`stack *ps;`

`{`

`int i,temp;`

`binarytreepointer null,setnull();`

`null = setnull();`

`temp = TRUE;`

`for (i=0;i<=(*ps).top;i++)`

`if ((*ps).stackarray[i] != null)`

`temp = FALSE;`

`return(temp);`

`}`

`overflow(ps)`

`/* Prints a message if the stack overflows. */`

`stack *ps;`

`{`

`printf("\n stack overflow ");`

`}`

`underflow(ps)`

`/* Prints a message if the stack underflows. */`

`stack *ps;`

`{`

`printf("\n stack underflow ");`

`}`

`printtree(ptree)`

`/* Prints the info field values of all`

`nodes of the binary tree tree.`

`*/`

`binarytreepointer *ptree;`

`{`

`binarytreepointer null,p,q,rightpointer;`

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

`stack s1;`

`null = setnull();`

`setstack(&s1);`

`p = *ptree;`

`while ((p != null) || !empty(&s1))`

`if (p != null)`

`{`

`printnode(ptree,p);`

`if (left(p) != null)`

`{`

`push(p,&s1);`

`p = left(p);`

`}`

`else`

`{`

`push(p,&s1);`

`p = right(p);`

`}`

`}`

`else`

`{`

`do`

`{`

`pop(&s1,&q);`

`if (!empty(&s1))`

`rightpointer = right(item(&s1));`

`else`

`rightpointer = null;`

`}while(!empty(&s1) &&`

`(q == rightpointer));`

`if (q != rightpointer)`

`p = rightpointer;`

`}`

`}`

`terminalcount(ptree)`

`/* Prints the number of terminal nodes`

`in the binary tree tree.`

`*/`

`binarytreepointer *ptree;`

`{`

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

`stack s2;`

`null = setnull();`

`setstack(&s2);`

`p = *ptree;`

`while ((p != null) || !empty(&s2))`

`if (p != null)`

`{`

`updatetncount(ptree,p,&s2);`

`push(right(p),&s2);`

`p = left(p);`

`}`

`else`

`pop(&s2,&p);`

`}`

`updatetncount(pt,p,ps)`

`/* Prints the number of terminal nodes in`

`binary tree tree when p points to the last`

`node in a preorder traverse of tree which`

`saves right pointers on stack s.`

`*/`

`binarytreepointer *pt,p;`

`stack *ps;`

`{`

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

`static int tncount;`

`null = setnull();`

`if (p == *pt)`

`tncount = O;`

`if ((left(p) == null) && (right(p) == null))`

`{`

`tncount++;`

`if (last(ps))`

`printf("\n The number of terminal nodes\`

`is %d",tncount);`

`}`

`}`

`replacefirstterminal(ptree,value)`

`/* Replaces the first terminal node, encountered`

`in a preorder traversal of binary tree tree, by a`

`new node with its info field set to the contents`

`of value.`

`*/`

`binarytreepointer *ptree;`

`int value;`

`{`

`binarytreepointer null,p,q,rightpointer;`

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

`stack s3;`

`null = setnull();`

`setstack(&s3);`

`p = *ptree;`

`while ((p != null) | | !empty(&s3))`

`if (p != null)`

`{`

`replacenode(ptree,p,null,&s,value);`

`if (left (p) != null)`

`{`

`push(p,&s3);`

`p = left(p);`

`}`

`else`

`{`

`push(p,&s3);`

`p = right(p);`

`}`

`}`

`else`

`{`

`do`

`{`

`pop(&s3,&q);`

`if (!empty(&s3))`

`rightpointer = right(item(&s3));`

`else`

`rightpointer = null;`

`}while (!empty(&s3) &&`

`(q == rightpointer));`

`if (q != rightpointer)`

`p = right pointer;`

`}`

`}`

`replacenode(ptree,p,null,ps,value)`

`/* If p points to the first terminal node, encountered`

`in a preorder traversal of binary tree tree that`

`saves the path to the root on stack s, then`

`replaces that node by a new node whose info field is`

`set to the contents of value.`

`*/`

`binarytreepointer *ptree,p,null;`

`stack *ps;`

`int value;`

`{`

`binarytreepointer q,ptr,avail(),left(),right();`

`if ((left(p) == null) && (right(p) == null))`

`{`

`ptr = avail();`

`setinfo(ptr,&value);`

`setleft(ptr,null);`

`setright(ptr,null);`

`if (p != *ptree)`

`{`

`q = item(ps);`

`if (left(q) == p)`

`setleft(q,ptr);`

`else`

`setright(q,ptr);`

`}`

`else`

`*ptree = ptr;`

`setstack(ps);`

`}`

`}`

`depth(tree)`

`/* Returns the depth of the binary tree tree. */`

`binarytreepointer tree;`

`{`

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

`if (tree == setnull())`

`return(0);`

`else`

`return(1 + max(depth(left(tree)),`

`depth(right(tree))));`

`}`

`max(i,j)`

`/* Returns the maximum of i and j. */`

`int i,j;`

`{`

`if (i >= j)`

`return(i);`

`else`

`return(j);`

`}`

# 7.5: Trees

## 7.5.1 Implementing Trees as Binary Trees

This implementation will not be pursued further but is similar in character to the sequential implementation for binary trees. This means that formulas can be derived to compute the array position of a node's predecessor and successors, which are important requirements for tree processing. Also, this representation is convenient for essentially static, healthy-looking (nonparse) trees.

Another representation is based on a natural generalization of the linked representation for binary trees. Simply expand each record so that it has as many pointer fields as it has subtrees. However, this leads to variable-length records, which are usually not desirable. The variable-length records occur because nodes need not all have the same number of successors. Further, it may not even be possible to predict in advance what the greatest number of successors will be.When it is known that the tree will be a k-ary tree, then all records could be made the same length, large enough to accommodate k subtree pointers. This gives a fixed record size but can result in considerable wasted storage for unused pointer fields within records. This is particularly true for sparse trees.

Surprisingly, there is a way to represent a tree as a binary tree, which then allows all records to be of fixed length. This is an important result. Since any tree can be represented by a binary tree, studying only binary trees is really no restriction at all.

Let us now look at how to represent a specific tree as a binary tree. Consider the tree of Figure 7.13(a). How can this tree be represented as a binary tree?

The binary tree is obtained as follows: First, create a root A of the binary tree to correspond to the root A of the tree. Next, pick any successor of A in the tree--say, B--and create a node B in the binary tree as A's left successor. Then take the remaining siblings of B, which are C and D in this case, and let C be B's right successor and D be C's right successor, in the binary tree. So far this yields the binary tree shown in Figure 7.13(b). If we view this procedure as the processing of node A of the tree, then the binary tree is completed by repeating this procedure for every other node of the tree. For example, after node B is processed (that is, its successors have been added to the binary tree), the result is Figure 7.13(c). The final binary tree created using this procedure appears in Figure 7.13(d).

# 7.6: Traversals of Trees

* It is not difficult to generalize tree traversal algorithms to obtain graph traversal algorithms.

To preorder traverse an ordered tree:

1. Access and process its root, then

2. Preorder traverse its subtrees in order.

To postorder traverse an ordered tree:

1. Postorder traverse its subtrees in order, then

2. Access and process its root.

## 7.6.1 Obtaining the Binary Tree for a Tree

Let the task for this example be the development of an algorithm to generate the binary tree corresponding to a general tree.

Nonrecursive Tree Preorder Traversal

1. Set p to t

2. Setstack_t(ts)

3. While p is not null or not empty_t(ts),

if p is not null, then

process(t,p)

For each successor pointer ps of node.p,

except next(p),

push_t(ps,ts)

Update p to next(p)

else

pop_t(ts,p)

This algorithm is a generalization of the nonrecursive preorder traversal of a binary tree that saves right pointers. In the binary tree case, the next subtree is the left subtree, and only one successor of the node just processed must be saved--the right successor. The difference is that now all the subtree pointers of the node just processed, except for the next one, must be saved.

Now that we have a general tree traversal, it will be adapted to our task. Let bt point to the binary tree to be generated by the algorithm. Recall the list-structure representation of a binary tree. Think of the leftpointer field of each node of bt as pointing to a sublist. This sublist contains all the successors of the corresponding node in t. Thus, in Figure 7.13(d), node A of the binary tree representation has a leftpointer field pointing to the sublist consisting of nodes B, C, and D. These are the successors of A in the general tree, Figure 7.13(a). Similarly, D has a leftpointer field pointing to the sublist consisting of I and J, the successors of D in the general tree.

Consequently, to produce bt, when a node of t is processed we must

Create a sublist consisting of all its successors

Set the leftpointer field of the corresponding node in bt to point to this sublist

#### Figure 7.14 Binary Tree BT Generated from General Tree T

Copy the info field of the node in t into the info field of the corresponding node in bt

The rightpointer fields of these nodes in bt serve as the link fields of the sublist.

Recall that, as we preorder traverse a general tree t, we are preorder traversing its corresponding binary tree, bt. That is, the order in which the nodes of t are accessed is exactly the same as the order in which the corresponding nodes of bt are accessed. Thus we can achieve a solution by preorder traversing both t and bt at the same time, and processing the corresponding nodes as described above. For example, if this were carried out on the general and final binary tree of Figure 7.13, and nodes A, B, E, F, G, and C had been processed, we would have generated the binary tree shown as Figure 7.14(b).

Suppose p points to the node currently being processed in t. Let pb point to the corresponding node in bt. In the example, p would now point to D of t and pb to D of bt.

After processing the node to which p points, we can update p to point to one of its successors, next(p), and stack on ts all pointers to the remaining successors. These pointers represent the latest postponed obligations for the preorder traversal of t. Next (p) is a function returning a pointer to the successor of p that is not stacked, or a null pointer if there are no successors. At the same time, to keep track of the postponed obligations for bt's preorder traversal, we will keep a parallel stack, bts. Only nonnull pointers will be pushed onto bts. When the top pointer in stack ts is popped, the top pointer in bts will also be popped. These pointers will then point to corresponding nodes--one in t, the other in bt. Storage can be created for the nodes of bt as the traversal proceeds by using avail to return a pointer to the available storage for a node, since a pointer variable implementation is used for the binary tree.

Nonrecursive Algorithm to Generate a Binary Tree Corresponding to a General Tree

1. Set p to t

If p is null

Set bt to null

else

bt = avail()

Set pb to bt

2. Setstack_t(ts)

Setstack_bt(bts)

3. While p is not null or not empty_t(ts),

if p is not null, then

process(t,bt,p,pb).

For each successor pointer ps of node.p, except next(p),

push_t(ps,ts)

If right(pb) is not null

push_bt(right(pb),bts)

p = next(p)

pb = left(pb)

else

pop_t(ts,p)

pop_bt(bts,pb).

The process algorithm to be used in the preorder traversal is:

Create(p,first)

Set leftptr.pb to first

Set info.pb to info.p

Notice that the traversal of the binary tree bt is embedded in the traversal of the general tree t. Also, suffixes have been used to distinguish the stack storing pointers to nodes of the general tree from the stack storing pointers to nodes of the binary tree. Finally, since the tree t is not ordered, the function next is free to pick any successor. The order in which the rest of the successors are placed on the stack is arbitrary but must determine the order in which create places them on the sublist. You should simulate this algorithm on the tree of Figure 7.13(a) to see how it works.

The correspondence between an ordered tree and its binary tree can now be defined more formally. In this case the binary tree corresponding to a tree is unique. An ordered tree t may be represented by a binary tree bt as follows:

Each node of t corresponds to a node of bt,

If node n of t corresponds to node nb of bt, then the leftmost successor of n in t corresponds to the left successor of nb in bt;

All other siblings of n in t form a right chain from the node in bt corresponding to the leftmost successor of n in t.

We may now give a recursive definition specifying an algorithm for generating the binary tree bt representing the general ordered tree t.

To generate a binary tree corresponding to an ordered tree:

If t is null

Set bt to null

else

Create the root node of bt corresponding to the root of t.

If t has a subtree, then generate the binary tree bt.left corresponding to the leftmost subtree of t,t.leftmost, and make the generated binary tree the left subtree of bt.

For every other subtree of t, in order, generate the binary tree corresponding to the subtree, and insert it at the end of the right chain of bt.left.

For illustration this algorithm is applied to the ordered tree in t in Figure 7.15(a).

First create the root of BT corresponding to the root of t shown in Figure 7.15(b). To carry out statement 2, note that t has three subtrees with B at the root of its leftmost subtree. We must thus generate bt.left to orrespond to Figure 7.15(c). To do this, apply the definition to this tree and obtain Figure 7.15(d) as its corresponding binary tree. Completing the first part of statement 2 for t yields the binary tree shown in Figure 7.15(e).

#### Figure 7.15 Generation of Binary Tree BT from an Ordered Tree T

To complete the second part of statement 2, generate the binary tree for the next subtree of t, with C at its root, and then insert it at the end of the right chain of B to obtain Figure 7.15(f). Finally, do the same for the last subtree of A, with D at its root, and complete the application to t, to obtain the result shown in Figure 7.15(g).

This is another example for which we found a recursive solution. Compare the clarity and conciseness of the recursive solution with that of the nonrecursive solution.

## 7.6.2 Backtracking: The n-queens Problem

Chess is played on a square board with eight rows and eight columns, just like a checkerboard. We can think of the board as a two-dimensional array, board (Figure 7.16).

A queen located in the jth row and kth column may move to a new position in one of the following ways:

To the right, or left, along its row

Up, or down, in its column

Up, or down, along its d1 diagonal

Up, or down, along its d2 diagonal

#### Figure 7.16 A Partial Chessboard Represented as a Two-Dimensional Array, BOARD

The n-queens problem is to find all ways to place n queens on an n X n checkerboard so that no queen may take another. As an example, the eight-queens problem is to find all ways to place eight queens on the chessboard so that no queen may take any other--that is, move into a position on its next move that is occupied by any other queen.

The question is how to solve the n-queens problem. At first glance this problem has little relation to trees, but let us see. It is not even clear that a solution exists for all n.

To construct a solution involves testing a partial construction to determine whether or not it can lead to a solution or must be abandoned as a dead end. This testing is the next question.

Consider a general tree, with each of its nodes representing a sequence of decisions on the placement of queens. Take the root to represent the initial situation, in which no decisions have yet been made. The root will have n successors. Each successor corresponds to a choice of row for the placement of the first queen. Each of these successor nodes, in turn, has n successors, corresponding to a choice of row for the placement of the second queen, and so on. The tree for the four-queens problem is shown in Figure 7.17.

Since exactly one queen must appear in each column in any solution, assume the ith queen is placed in column i. Hence, each path, from the root to a node at depth i in the tree, specifies a partial construction in which the first i queens have been placed on the board. The path indicated in the four-queens tree specifies a partial construction in which the first, second, and third queens have been placed in rows 2, 4, and 1 (and columns 1, 2, and 3), respectively. The tree helps us visualize all possible solutions and provides a framework in which to view what we are doing.

## 7.6.3 Depth-first

You, as the programmer, do not know whether a solution exists for every n. Therefore, initialize a flag, found, to false, and have process set found to true if it finds a solution. Upon exiting from the loop body, test found, and if it is false print "No solution." The resultant algorithm for a backtracking preorder traversal is as follows:

Backtracking Preorder Tree Traversal

1. Set p to the root of t.

2. Set found to false.

3. Set the stack to empty.

4. While p is not null or the stack is not empty,

if p is not null, then

if p is feasible, then

process(p),

push all successors of node.p onto the stack except next(p),

move down in t by setting p to next(p),

else

backtrack in t by popping the stack and setting p to the popped value,

else

backtrack in t by popping the stack and setting p to the popped value;

print no solutions.

The function next(p) is assumed to return a null value if node.p has no successors. If only one solution is to be found and printed, only the test of the while loop must be changed. It should become "(p not null or stack not empty) and (not found)." The process algorithm to be used with the backtracking preorder traversal is as follows:

If node.p is a terminal node, then

1. Print the solution, and

2. Set found to true.

The algorithms developed in this section are quite general. They are applicable to any problem that can be reduced to a backtracking traversal (like the n-queens problem). They should be viewed as general tools for problem solving. We must now specialize them to the n-queens problem so that they are detailed enough to implement as a function. Data structure decisions, specifically the implementation of the current board configuration, must be made along the way.

The tree is not actually stored in memory; it was used as a conceptual aid in formulating the problem abstractly. As a result, the problem has been recognized as one that may be solved by a general tree backtracking procedure. It is not necessary to refer to the tree at all, but we have done so here to place the problem in this more general context, and we continue with this approach.

Suppose p points to a node at depth k. The depth of the node specifies the placement for the kth queen, column k. P itself determines the choice of row. In this way p corresponds to a particular row and col pair and vice versa. A nonnull value for p corresponds to a column and row value <n + 1. Initializing p to the first successor of the root corresponds to setting row to 1 and col to 1.

Next must have row and col as parameters; it simply increases col by 1 and sets row to 1. As the traversal proceeds, row and col vary in a regular way. This can be used to advantage. Instead of pushing all successors of node.p onto the stack, which would involve n - 1 entries, simply push the current value of row. Then the backtracking task can be carried out by adding 1 to the current value of row when this value is less than n. If it equals n, the stack must be popped, row set to the popped value plus 1, and col set to col-1.

To implement the crucial test, "p feasible," we use a function feasible to return the value true when p is feasible and false otherwise. Feasible must have row and col as parameters and must have access to information about the current board configuration. It must determine if placing a queen in the position specified by row and col will allow it to "take" one of the currently placed queens. If a queen may be taken, it must return "false," otherwise "true."

We could use an n X n two-dimensional array board to keep track of the current board configuration. If we did this, feasible would have to traverse through the row, column, and diagonals specified by row and col in order to determine what value to return. This checking must involve all entries in many rows and columns. Since feasible is invoked in the loop body of the backtracking preorder traversal algorithm, it is executed once for every node of the tree that is accessed. Operations that appear in loop bodies should be done efficiently since they have a significant effect on the overall efficiency of the implementation.

To do its job, feasible must know whether or not the row, col, and the diagonals specified by row and col are occupied. If this information can be efficiently extracted and made available, feasible will be more efficient. We now see exactly what information is required and proceed to the details involved in efficiently extracting it.

Consider Figure 7.16. Notice that entries [j, k], [j + 1, k - 1], and [j - 1, k +1] all lie along the d1 diagonal. Notice also that j+ k = (j+ 1) + (k - 1) = (j- 1) + (k + 1). This means that all entries on the diagonal d1, determined by j and k, have the same row + col sum: j + k. The same is true of differences along d2. That is, all entries on the diagonal d2, determined by j and k, have the same row minus col difference: j - k. Suppose we keep information about the current board configuration as follows:

r[j]

Is true if the current board configuration has no queen in the jth row, and is false otherwise.

d1[j + k]

Is true if the current board configuration has no queen along the diagonal d1 with row + col sum j + k, and false otherwise.

d2[j - k]

Is true if the current board configuration has no queen along the diagonal d2 with row - col sum j - k, and false otherwise.

Feasible can now simply return the value of (r[j] and d1 [j + k] and d2[j - k]). The arrays r, d1, and d2 require storage for n, 2(n - 1), and 2(n - 1) entries, respectively, and must be properly initialized, but feasible now takes constant time to execute. Also, when row and col are changed, these changes must be reflected in r, d1, and d2. What we have done amounts to finding a way to store the current board configuration so that the operations performed on it by the algorithm are done efficiently. R, d1, and d2 have indices that range from 1 to n, 2 to 2n, and -(n - 1) to (n - 1), respectively. Since C does not allow such array indices, it is necessary to refer in the program below to corresponding entries in arrays whose indices will range from 0 to n - 1, 0 to 2(n - 1), and 0 to 2(n - 1), respectively.

Finally, we must implement the printing of a solution in process . This can be done by printing the sequence of values stored on the stack. They specify the rows in which queens 1 to n were placed. To do this we will need a stack operation item. It returns a copy of the ith stack entry, which represents the row in which the (i+1)th placed queen (the queen in column i) appears. When i is zero, it returns a copy of the top entry.

The backtracking traversal algorithm that was developed and applied to this problem is a general tool for problem solving. It may be adapted, for example, to solving a maze, finding good game-playing strategies, and translating high-level language programs.

The nonrecursive solution may be written as follows.

Nonrecursive n-queens Program

`# include <stdio.h>`

`main()`

`/* Reads in n and prints all solutions`

`to the n-queens problem.`

`*/`

`{`

`int n;`

`printf("\n n = ?");`

`scanf("%d",&n);`

`queens(n);`

`}`

`#define NLIMIT 20`

`typedef int rowcheck[NLIMIT];`

`typedef int diagonalcheck1[2*NLIMIT-1];`

`typedef int diagonalcheck2[2*NLIMIT-1];`

`#define SLIMIT 20`

`typedef int whatever;`

`typedef struct`

`{`

`whatever stackarray[SLIMIT--1];`

`int top;`

`}stack;`

`setstack(ps)`

`/* Sets stack s to empty. */`

`stack *ps;`

`{`

`(*ps).top = --1;`

`}`

`empty(ps)`

`/* Returns true only if stack s is empty. */`

`stack *ps;`

`{`

`return((*ps).top == -1);`

`}`

`push(value,ps)`

`/* Inserts contents of value as`

`the top entry on stack s.`

`/*`

`whatever value;`

`stack *ps;`

`{`

`if((*ps).top == (SLIMIT-1))`

`overflow(ps);`

`else`

`{`

`(*ps).top = (*ps).top + 1;`

`(*ps).stackarray[(*ps).top] = value;`

`}`

`}`

`pop(ps,pvalue)`

`/* Removes the top entry of stack s`

`and copies its contents into value.`

`*/`

`stack *ps;`

`whatever *pvalue;`

`{`

`if(empty(ps))`

`underflow(ps);`

`else`

`{`

`*pvalue = (*ps).stackarray[(*ps).top];`

`(*ps).top = (*ps).top - 1;`

`}`

`}`

`whatever item(i,ps)`

`/* Returns a copy of the ith`

`entry in stack s. When i is`

`zero it returns a copy of`

`the top entry.`

`*/`

`stack *ps;`

`{`

`return((*ps).stackarray[(*ps).top-i]);`

`}`

`overflow(ps)`

`/* Prints a message if the stack overflows. */`

`stack *ps;`

`{`

`printf("\n stack overflow ");`

`}`

`underflow(ps)`

`/* Prints a message if the stack underflows. */`

`stack *ps;`

`{`

`printf("\n stack underflow ");`

`}`

`queens(n)`

`1 a backtracking preorder traversal`

`/* Prints all solutions to the n-queens problem */`

`int n;`

`{`

`stack s;`

`#define TRUE 1`

`#define FALSE 0`

`int i,row,col,found;`

`rowcheck r;`

`3 r, d1, and d2 will contain the board configuration`

`diagonalcheck1 d1;`

`diagonalcheck2 d2;`

`col = 1;`

`2 col and row determine the next placement attempt`

`row = 1;`

`for(i=0;i<=n-1;i++)`

`r[i] = TRUE;`

`for(i=0;i<=2*n-2;i++)`

`d1[i] = TRUE;`

`for(i=0;i<=2*n-2;i++)`

`d2[i] = TRUE;`

`found = FALSE;`

`setstack(&s);`

`while(((col < n+1)&&(row < n+1)) || !empty(&s))`

`if((col < n+1)&&(row < n+1))`

`if(feasible(row,col,r,d1,d2,n))`

`{`

`process(row,col,&found,&s,n);`

`push(row,&s);`

`r[row-1] = FALSE;`

`d1[row+col-2] = FALSE;`

`d2[row-col+n-1] = FALSE;`

`col = col + 1;`

`row = 1;`

`}`

`else`

`row = row + 1;`

`else`

`{`

`pop(&s,&row);`

`col = col - 1;`

`r[row-1] = TRUE`

`d1[row+col-2] = TRUE;`

`d2[row-col+n-1] = TRUE;`

`row = row + 1;`

`}`

`if(!found)`

`printf("\n NO SOLUTIONS");`

`}`

`feasible(row,col,r,d1,d2,n)`

`/* Returns true only if the placement of the`

`next queen in position col,row does not`

`allow any queen to take another under`

`the current board configuration given`

`by r,d1,d2.`

`*/`

`int row,col, n;`

`rowcheck r;`

`diagonalcheck1 d1;`

`diagonalcheck2 d2;`

`{`

`return(r[row-1]&&d1[row+col-2]&&d2[row-col+n-1]);`

`}`

`process(row,col,pfound,ps,n)`

`/* If the partial solution is a complete`

`solution then it is printed and`

`found is set to true.`

`*/`

`int row,col,*pfound,n;`

`stack *ps;`

`{`

`int i;`

`whatever item();`

`if(col == n)`

`{`

`for(i=n-1;i>=1;i--)`

`printf("\n COL %d ROW is %d----",`

`n-1,item(i-1,ps));`

`printf("\n COL %d ROW is %d----\n",`

`n,row);`

`*pfound = TRUE;`

`}`

`}`

You may be tempted to try a more analytic approach to this problem so as to eliminate the need for all this searching. Be forewarned that famous mathematicians also attempted to analyze this problem but had difficulty solving it other than by backtracking! Actually, there are no solutions for n = 1, 2, and 3, and at least one solution for all n4. For the curious, the number of solutions for n up to 15 are:

`    N      4      5          6    7      8       9         10`

`Solutions  2      10         4    40    92      352        724`

`    N        11        12         13        14          15`

`Solutions  2,680     14,200     73,712    365,596    2,279,184`

if p is not null, then

if p is feasible, then

process(p)

push all successors of node.p onto the stack

pop(sp)

else

pop(s,p).

This implementation also represents a preorder tree traversal. The stack is used to store and recall postponed obligations. It can be further modified by changing the stack to a queue and replacing empty, push, and pop by the corresponding queue operations. Pop must return null if called when the queue is empty. The result is another modified general tree traversal, a backtracking breadth-first traversal. It accesses the nodes in level order. In contrast, the backtracking preorder traversal presented earlier might be called a backtracking depth-first traversal. Removing the "p is feasible" test of the backtracking breadth-first traversal turns it into a breadth-first traversal. You should convince yourself that this version leads to the nodes of Figure 7.13(a) being accessed and processed in the order A, B, C, D, E, F, G, H, I, J, K, L, M. Keep in mind that in this application the root node was never considered. The difference between a backtracking traversal and a traversal is that backtracking tests for feasibility. This allows tree paths to be ignored when it can be determined that they cannot lead to a solution.

## 7.6.5 Branch and Bound

Nonrecursive Branch and Bound Traversal

1. Set p to t.

2. Set bag to empty.

3. While p is not null

if p is feasible, then

i. process(t,p), and

ii. add each successor pointer of p to the bag;

Select a pointer from the bag and set p to it.

# 7.7: More on Recursion, Trees, and Stacks

Further, we can now see that recursion clarifies because it hides the bookkeeping required by the tree traversal and because it elucidates the structure that must be inherent in the problem in order for a recursive solution to be found in the first place. Although it is an extremely powerful tool for these reasons, it must be applied with care. The purpose of this section is to provide some insight into the nature of those problems where a more skeptical approach is wise.

## 7.7.1 Balanced Binary Trees

The binary tree of Figure 7.18(a) is balanced; the binary tree of (b) is not. Balanced trees are important in information retrieval applications; they will be discussed fully in Chapter 9. In information retrieval, the data are stored at the tree's nodes. The depth of the tree determines the search times for retrieval and, with balanced trees, the tree's depth is controllable and can be limited, as will be shown in Chapter 9. Here we consider the "worst case" of such trees.

#### Figure 7.19 A Fibonacci Tree of Depth 4

The Fibonacci numbers are a well-known sequence of integers defined by the following recursive definition:

`F0 = 0,   F1 = 1,`

`Fn = Fn-1 + Fn-2    for n > 1`

The first few are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . These numbers seem to appear in the most unexpected places. In computer science they often arise in the analysis of algorithms. The number of nodes in a Fibonacci tree of depth d can be shown to be Fd+2 - 1 (see Exercise 34b). For example, if d is 4, then Fd+2 - 1 = F6 - 1 = 8 - 1 = 7.

The task now is to develop an algorithm to generate a Fibonacci tree of depth d. If possible, apply the method of recursion to find a recursive definition of the solution.

Clearly, if d = 0, there is only one Fibonacci tree of depth d, the null binary tree. If d = 1, there is only one Fibonacci tree of depth d, the tree with one node--its root.

Any subtree of a balanced binary tree must also be balanced, or else the tree itself would not be balanced. Any subtree of a Fibonacci tree must therefore be balanced and must also be a Fibonacci tree. Otherwise it could be replaced by a Fibonacci tree of that depth with fewer nodes. This is the key to the recursive solution. We can now construct a Fibonacci tree of depth d > 1 as follows: Since d > 1, the Fibonacci tree must have a root, and its two subtrees must be Fibonacci trees. One (say, the right) must have depth d - 1 (so the tree itself has depth d). The other, the left subtree, must be a Fibonacci tree and must differ in depth from d - 1 by at most 1. Hence it must have depth d - 2 or d - 1. It has just been demonstrated that a Fibonacci tree of depth d - 1 has at least one subtree of depth d - 2. Hence the Fibonacci tree of depth d - 1 has more nodes than the Fibonacci tree of depth d - 2. Thus the left subtree of the Fibonacci tree being constructed must have depth d - 2. (Why?) This gives the complete recursive solution.

To construct a Fibonacci tree of depth d:

1. If d = 0, then construct the null tree,

2. else if d = 1, then construct the tree with one node, its root,

3. else if d > 1, then

a. construct a root,

b. construct a Fibonacci tree of depth d - 2 and make it the left subtree of the root, and

c. construct a Fibonacci tree of depth d - 1 and make it the right subtree of the root.

The explicit constructions are given by the algorithm's statements 1 and 2 for d = 0 and d = 1. Statement 3 gives the implicit construction for d > 1. You should apply this definition to the case d = 4, and confirm that it constructs the example given earlier of a Fibonacci tree of depth 4. It should also be clear that other Fibonacci trees of depth 4 exist.

The recursive program can be written directly from the definition.

`fibonaccitree (d, ptree)`

`/* Creates a Fibonacci tree, tree, of depth d. */`

`int d;`

`binarytreepointer *ptree;`

`{`

`binarytreepointer tl, tr, avail ( );`

`*ptree = avail ( );`

`if (d == 0)`

`*ptree = NULL;`

`else if (d == 1)`

`{`

`records [*ptree].leftptr = NULL;`

`records [*ptree].rightptr = NULL;`

`}`

`else`

`{`

`fibonaccitree (d-2,&tl);`

`records [*ptree].leftptr = tl;`

`fibonaccitree (d-1,&tr);`

`records [*ptree].rightptr = tr;`

`}`

`}`

For concreteness, we have chosen to implement the constructed tree using a linked representation. The tree itself will be stored in the records array (Section 7.4.2) with the fields of a record being info, leftptr, and rightptr.Records is assumed to be a global variable. When the routine returns, tree will point to its root record in the array representation.

Using implementation with pointer variables for the binary tree, the procedure becomes the following.

`fibonaccitree(d,ptree)`

`/* Creates a Fibonacci tree, tree, of depth d. */`

`int d;`

`binarytreepointer *ptree;`

`{`

`binarytreepointer tl, tr;`

`*ptree = malloc (sizeof(binarytreerecord));`

`if (d == 0)`

`*ptree = NULL;`

`else if (d == 1)`

`{`

`(*ptree)->leftptr = NULL;`

`(*ptree)->rightptr = NULL;`

`}`

`else`

`{`

`fibonaccitree (d-2, &tl);`

`(*ptree)->leftptr = tl;`

`fibonaccitree (d-1, &tr);`

`(*ptree)->rightptr = tr;`

`}`

`}`

Finally, for contrast, the function may be written treating the tree as a data abstraction, as follows.

Recursive Version 3--The Tree Is Treated as a Data Abstraction

`fibonaccitree(d,ptree)`

`/* Creates a Fibonacci tree, tree, of depth d. */`

`int d;`

`binarytreepointer *ptree;`

`{`

`binarytreepointer null,tl,tr,avail( ),setnull( );`

`null = setnull( );`

`*ptree = avail( );`

`if (d == 0)`

`*ptree = null;`

`else if (d == 1)`

`{`

`setleft(*ptree, null);`

`setright(*ptree, null);`

`}`

`else`

`{`

`fibonaccitree(d-2,&tl);`

`setleft(*ptree, tl);`

`fibonaccitree(d-1,&tr);`

`setleft(*ptree, tr);`

`}`

`}`

## 7.7.2 Trading Storage for Time

#### Figure 7.20 Execution Tree for Depth d = 6

Figure 7.20 shows a rather healthy-looking (nonsparse) tree with depth d = 6. This holds true for any value of d and means that while the storage is not excessive, the number of nodes in the tree will be O(d), where = (1 + )/2.* This is because

The execution tree for Fibonaccitree will always "resemble" the tree it is constructing.

The depth of an execution tree determines the size of the underlying stack needed for the program to execute properly.

The number of nodes in a Fibonacci tree of depth d is Fd+2 - 1.

Hence the execution time will increase exponentially with d. A close inspection reveals that many identical tasks or problems are solved repeatedly during its execution. For example, d = 0, 1, 2, 3, and 4 are solved 5, 8, 5, 3, and 2 times, respectively. This is what causes the excessive execution time and illustrates the situation to be wary of. When the same problems occur repeatedly, the efficiency can be increased if the algorithm can be modified to save the results for these problems so they may be used directly when needed instead of being regenerated by recursive calls. Of course, if this requires excessive storage, then such an approach won't do. Excessive storage is needed when an excessive number of distinct problems must be solved and their results saved. Still, this represents a viable strategy when applicable, as is the case here.

* In fact, the number of nodes will be 2Fd+1 - 1.

Notice that a Fibonacci tree of depth d 2 can be constructed even if only Fibonacci trees of depth d - 2 and d - 1 are known. All that is necessary is to create a root node and append the tree of depth d - 2 as its left subtree and the tree of depth d - 1 as its right subtree. Consequently, the Fibonacci tree of depth d can be obtained by constructing the trees for depth 0, 1, 2 . . . , d in turn, while retaining only the lastest two. This gives the nonrecursive solution:

An Efficient Nonrecursive Version

If d = 0, then

set t to null;

else if d = 1, then

a. create a root node

b. set t to point to the root node;

else

c. set tl to null,

d. create a root node,

e. set tr to point to the root node, and

f. for k from 2 to d,

i. create a root node with tl its left subtree and tr its right subtree

ii. set t to point to the root node

iii. set tl to tr and tr to t.

This solution is efficient in both execution time and storage (see Exercises 16 and 17 of Chapter 4 for a related example).

Although it was possible to cut down drastically on the number of Fibonacci trees retained in this solution, such a saving not always possible. Sometimes solutions to all the problems generated by recursive calls will need to be retained. Even so, when this number is not excessive and an appropriate data structure can be found in which to store and efficiently access a solution when needed, then execution time can be improved. This is another instance of what we have frequently seen: time may be traded for storage.

It is hoped that you do not feel we have been barking up the wrong trees! Perhaps you even agree with the humorist Ogden Nash:

I think that I shall never see

A billboard lovely as a tree.

Indeed, unless the billboards fall

I'll never see a tree at all.

# Exercises

b. What is the maximum number of nodes that a binary tree of depth d can have?

a. how many distinct binary trees are there with 4 nodes?

b. Can you find a formula for the number of distinct binary trees with n nodes? This formula bt(n) may be expressed in terms of bt(k) for k < n.

b. Do you notice anything striking about the inorder listing?

b. What is the necessary value for limit in order to guarantee that the traversal will work with the stack, for any binary tree with n nodes?

Both binary trees have identical listings. This cannot happen with preorder and inorder listings. That is, we cannot find two distinct binary trees that have identical preorder and inorder listings. The same is true for postorder and inorder listings. Find an algorithm that will create the unique binary tree that is thus determined by its preorder and inorder listings.

b. What about for inorder and postorder traversals?

` 5    `

` 8  L   0`

`-1  O  -1`

` 3  U   4`

`-1  S  -1`

`-1  T  -1`

Three records appear in the input in the order in which they would be accessed by a preorder traversal. Assume the head value is read into fred, and preorder traverse is called. Write a process routine that will turn preorder traverse into a routine that reads the records of the binary tree into the leftptr, info, and rightptr fields properly.

b. Same as Exercise 11(a), but assume the records are given in the order in which they would be accessed in a postorder traversal.

`          leftptr  info  rightptr`

`           1    0    R       0`

`           2    3    W       4`

`           3    5    R       0`

`sample 7   4    0    C       0`

`           5    4    E       6`

`           6    0    T       0`

`           7   10    C       3`

`           8    6    A       3`

`           9    1    B       4`

`          10    1    O       0`

b. What would leftptr, info, and rightptr look like if all the terminal nodes of sample were deleted in Exercise 12?

b. What binary tree with n nodes will require the largest array for its sequential representation?

b. Write a function that, given a binary tree t and two pointers p and q to nodes of t, returns a value true if node.q is a successor of node.p and a value false otherwise.

c. Write a function that does the same thing as Exercise 18(b), except that the function returns a value true if node.q is in the subtree of node.p and a value false otherwise.

a. Describe this binary tree.

b. What general tree would have r as its binary tree under the transformation of Section 7.5.1?

b. What does your function do if t1 and t2 are the same tree?

c. How will your solution change if a sequential representation is used?

#### (b) Output

b. Write a routine that deletes node.q if it is a successor of node.p in a binary tree.

b. Create a function to interchange all left and right subtrees, except that the interchanged version of the original tree will be created as a new tree, leaving the original tree unchanged. Assume pointer variables are used for its implementation.

b. Do the same task, except that the binary trees need have only the same structure.

b. If the maze has loops, what modifications must be made in your solution so that the algorithm works correctly?

b. Modify the preorder traversal algorithm so that it produces the transformed tree by processing the nodes of t in breadth-first order. (Hint: Consider the queue.)

(A(B(E, F, G), C(H), D(I(K, L, M), J)))

This corresponds to the general tree:

Suppose that input is given by such a parenthesized expression. Can you find an algorithm that will create the general tree from it? Assume that the general tree will be represented in memory as a collection of lists of successors, with one successor list for each node.

b. What is the connection between parenthesized expressions and a listing of nodes in the order in which they are accessed by a preorder traversal?

Left(t) and right(t) are, respectively, the left and right subtrees of t.

a. If t is the binary tree that follows, then what is result(t)?

b. What does result do?

32. T1 and t2 point to binary trees represented using pointer variables.

`check (t1,t2)`

`binarytreepointer t1,t2;`

`{`

`binarytreepointer null,setnull();`

`null = setnull();`

`if(((t1 == null) && (t2 == null)) || ((t1 != null)`

`&& (t2 != null)))`

`return(check(t1->leftptr,t2->leftptr)`

`&& check(t1->rightptr,t2->rightptr));`

`else`

`return (FALSE);`

`}`

a. Find the function value if it is invoked for trees t1 and t2.

b. What does check do?

`b(0) = 1`

`b(n) = b(0) X b(n - 1) + b(1) X b(n - 2) + b(2)b(n - 3) + . . .`

`+ b(n - 1) x b(0) n > 0`

b. Find a connection between the number of distinct binary trees with n nodes and b(n).

b. Find a recursive definition for F(d), the number of nodes of a Fibonacci tree of depth d.

b. Write a recursive function terminal to delete all terminal nodes of a binary tree using pointer variables.

# Suggested Assignments

Also discuss the connection between the lists used in the case study and the binary tree representation of a general tree.