*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**depth-first and breadth-first traversals*

*Clarifies the relation between recursion, trees, and stacks**Discusses recursive solutions to show**when they are efficient**how to improve them*

Formally, * trees* are collections of nodes. Trees derive both their appearance and their name from the lines, known as

The mathematics of trees has always been of interest and is discussed quite thoroughly by Knuth [1973a]. In this chapter we consider fundamentals and introduce special trees as they are needed in subsequent chapters.

As indicated in Figure 7.1, there are many ways to depict *inclusion* or *hierarchical relationships*. Each part of the figure conveys the same information about the relations between objects *A* to *J*. Figure 7.1(a) uses indentation reminiscent of program structure, or Pascal, COBOL, and C record structure, to convey inclusion. Figure 7.1(b) uses nested blocks or sets, while Figure 7.1(c) has nested parentheses. The last, Figure 7.1(d), uses lines that branch out like a tree turned upside down. This is how the data structure that is the topic of this chapter, the tree, is depicted.

If Figure 7.1(a) is being used to represent the structure of a C record, then the structure shows that record *A* includes three fields, *B*, *C*, and *D*, or that *D *includes two subfields, *I* and *J*. The *tree* of Figure 7.1(d) captures this inclusion information. To a C compiler, it is also important that field *B* comes before *C* and that *C* precedes *D*. When such ordering information is needed, we use * ordered trees.* To capture order, as well as inclusion information, Figure 7.1(d) must be an

Much of the terminology for the tree data structure is taken from botany and is therefore familiar and colorful. For instance, *A* of the tree in Figure 7.1(d) is at the * root* of the tree. The tree consists of three

Besides these two kinds of trees, there are binary trees. A * binary tree* is either

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

The lines used to indicate a left and right subtree are called *branches*. Branches show the relationship between nodes and their subtrees. In Figure 7.3 the nodes are numbered 1 to 20 for easy reference. Node 5 has a * predecessor* (node 2), a

Follow the branch from node 1 to node 2 or 3 and you come to the left or right subtree of node 1. Its right subtree is shown in Figure 7.4. Similarly, each node has a left and a right subtree. Nodes with at least one successor are called * internal* nodes. Those with no successors are called

By definition, the root of a binary tree is at **depth****1** . A node whose path to the root contains exactly *d* - 1 predecessor nodes has depth *d*. For example, node 10 in Figure 7.3 is at depth 4. This is the * path length* of the node. The longest path length is called the

What if the range of the integers was not known? Sufficient storage is not available for an array to store counts for all possible integers. What is required is a data structure that can be dynamically extended to accommodate each new integer and its count as the integer is encountered in the input. This data structure must be searched to see if the new integer already appears. If it does, its count is increased by 1 . Should the integer not appear, it must be inserted with its count set to 1. A special tree, a binary search tree introduced in Chapter 9, is convenient to use for this data structure. This tree allows the search for an integer to consider only nodes along a particular path. At worst, this path must be followed from the root to a terminal node. Thus the longest search time will be determined by the depth of the tree. The same data structure and the depth measure are important for the related problem, "Produce an index for a book." Now, instead of storing integer counts, the position of each occurrence of a word must be retained. Do you see the possibility of storing dictionaries of modest size in binary search trees?

Binary trees need not have such a compact look as that of Figure 7.3 but can appear sparse, as in Figure 7.5. A compact binary tree like Figure 7.3 is called a *complete* binary tree. To be more precise, a binary tree of depth *d* is a * complete *binary tree when it has terminal nodes only at the two greatest depths.

*This section can be omitted on first reading.

Let us take a moment here to derive two important relations between the depth, *d *and the number of nodes, *n*, in a binary tree. First note that in any binary tree there is at most one node at depth 1, at most two nodes at depth 2, and, in general, at most 2* ^{k}*-1 nodes at depth

n2- 1^{d}

The minimum possible depth, *d*_{min}, for a binary tree with *n* nodes will be given by

d_{min}= lg (n+ 1)

The nodes of binary trees may be used to store information. For example, the nametable of Section 6.5 could be implemented by storing each of its records at a node of a binary tree. Just as lists are referred to by name, the tree can be named, say nametable. Obviously, nametable must have records inserted into it, deleted from it, and searched for in it. Insertion, deletion, search, and traversal are the basic tree operations.

Assume that each node of a binary tree is represented by a record containing an information field, a left pointer field, and a right pointer field. The notation node.p stands for the record or node pointed to by the variable p.

p = avail();

setinfo(p,&value);

setleft(p,null);

setright(p,null);

setright(predecessor,p);

Setinfo copies the contents of the storage pointed to by its second parameter into the info field of the record pointed to by its first parameter. Note that it is defined somewhat differently from the setinfo used in previous chapters. Setleft and setright copy the contents of their second parameter into the proper field of the record pointed to by their first parameter. Notice that setleft is used to set the left pointer of the new record; similarly for setright. However, setright is also used to change the right pointer of the predecessor record so that it points to the new record, which is now its right node. Thus setleft and setright can be used to set pointers for any node in the tree. Together with setinfo and avail, these functions reflect the binary tree's implementation details. The code for the insertion itself is independent of the implementation.

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

Left is analogous to right. The decision is required in order to know whether it is predecessor's left or right successor that is to be deleted. Again, if the deleted node's storage may be reclaimed, care must be taken not to lose the pointer to it. Deletion of an internal node must take into account what is to be done with the node's subtrees.

We have seen examples whose solution includes a traversal through a collection of records in an array or a list. A traversal through a collection of records stored in a binary tree is also the basis for the solution to many problems. We will consider three distinct ways to traverse a binary tree: (1) preorder, (2) inorder, and (3)postorder.

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

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.

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.

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

Nonrecursive Version Saving Right Pointers on a Stack

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.

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();

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.

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

If p points to the current record to be processed, then when p points to the root of the traversed tree tree, process has been called for the first time, so it must set tncount to zero. But how can process recognize when p points to the last node so that tncount can be printed? To do this, process must have access to the stack s. When s contains no nonnull pointers and node.p is a terminal node, then node.p is the last node. Assume that a function last returns *true *if s contains no nonnull pointers and *false* otherwise. Consequently s must be a parameter of, or global to, process. Finally, we must assume that only nonnull binary trees are to be considered since process is invoked by preorder only when tree is not null. Process may now be defined as follows.

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);

}

}

The second example concerns the problem of inserting a new node in the binary tree tree in place of the first terminal node encountered in a preorder traversal of tree. The information field value of the new node is to be copied from that of the record value.

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 final example involves writing a function depth to return the depth of a binary tree as its value.

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.

This section introduces three ways to implement a binary tree.

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

The sequential representation uses an array to store information corresponding to each node of a tree. Consider the binary tree shown in Figure 7.9. Its depth is 5 and it has fourteen nodes. The nodes are numbered in a special way. This numbering may be obtained by preorder traversing the tree and, as each node is accessed, assigning it a node number. The root is assigned 1, each left successor of a node is assigned twice the number of its predecessor, and each right successor is assigned one more than twice the number of its predecessor. With nodes numbered in this way, the predecessor of node i is numbered i/2 (integer divide), its left successor is numbered 2*i, and its right successor 2*i+1.

A binary tree data structure can also be implemented by representing each node of the tree as a record with three fields:

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 2* ^{d}* - 1, where

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);

}

Another way to represent a binary tree is indicated in Figure 7.11. Each node's record is made complex. A complex record's sublist points to the representation of the node's left subtree. The result is that btree is implemented as the list structure lstree. Abstractly, binary trees are a special case of list-structures, but there are list-structures that do not correspond to binary trees. However, in computer science the term *tree* usually implies zero or restricted sharing of storage, whereas the term *list-structure* or *list* implies the possibility of more general sharing of storage.

So far we have considered only binary trees, but trees may have nodes with more than two successors. This is the case in the tree of Figure 7.1, where the nodes have up to three successors. It would be natural to assume that binary trees are a special case of trees, but the tree literature does not treat them this way. The formal definition of a *tree*, as opposed to a binary tree, is as follows: A **tree**** **is a root node with subtrees t_{1}, t_{2}, . . . , t* _{n}* that are themselves trees and have no nodes in common.

Formally there are no null trees (although there are null binary trees), so each tree has at least one node, its root. It is convenient nonetheless to refer to null trees, so the terminology applied to binary trees also applies to trees. The important distinction is that no order is imposed on the subtrees of a tree, whereas for binary trees there is a distinct left and right subtree. Consequently, when trees are depicted, it makes no difference in what order subtrees are drawn; any order represents the same tree. When order among the subtrees is to be imposed, they are called *ordered trees*. For example the structures in Figure 7.12, when viewed as binary trees, represent two distinct binary trees, since their left and right subtrees differ, but they represent the same tree when viewed as trees.

When a constraint is imposed limiting the number of successors of any node to at most *k*, the tree is called a **k-*** ary* tree. Such trees may be implemented by generalizing the sequential representation for binary trees. The nodes are numbered as before, except the

Applying this procedure, given any tree, a corresponding binary tree can be constructed. The specific binary tree generated will depend on the order in which successors are taken in the tree. For instance, had C been selected initially as the first successor of A, then the resultant binary tree would be different. If the ordering of each node's successors is specified and they are taken in the specified order, then the construction creates a unique binary tree for each tree. In any case, a tree with *n* nodes will correspond to a binary tree with *n* nodes. It is not difficult to find an algorithm that, given a binary tree with no right subtree, can reverse the construction and generate the tree it represents. This means that when the tree is ordered, there is a *unique* binary tree that can be constructed to represent it. Conversely, given a binary tree with no right subtree, there is a unique tree that it represents, which can also be constructed. Hence there are exactly as many trees with *n* nodes as there are binary trees with *n* nodes and no right subtrees.

If we define an * ordered forest* as an ordered collection of ordered trees, then each tree has its unique binary tree representation. Can you see how to append these binary trees to the binary tree representing the first ordered tree of the ordered forest to obtain a binary tree representing the forest? (

In this section algorithms are developed for traversing trees and are applied to two examples. The second example should be studied carefully, because it illustrates an important modified traversal of trees that has many applications. Assuming the trees are ordered, it makes sense to refer to a tree's *first* subtree, *second* subtree, and so on. If an order is not given, the programmer can impose one.

When trees are used to store data at their nodes, then tree traversals give a means to access all the data. However, a tree might be used to represent a maze or all routes from Philadelphia to San Francisco. Traversal of the tree then provides the means to find exits from the maze or the shortest route across the country. The maze and the routes must not intersect. When they do, a more general data structure, a *graph*, is needed for their representation. Unlike trees, a * graph* allows more than one path between its nodes. * Should a tree contain family relationships by storing an individual's record at a node, a traversal allows the parent (predecessor) or the children (successors) of an individual to be found.

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

The preorder and postorder traversals of binary trees generalize quite naturally to ordered trees.

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.

There is no natural inorder traversal of trees. Preorder and postorder traversals of a tree correspond, respectively, to preorder and inorder traversals of its corresponding binary tree. The preorder and postorder access sequences for the tree of Figure 7.13(a) are ABEFGCHDIKLMJ and EFGBHCKLMIJDA. You should confirm that a preorder and an inorder traversal of the binary tree of Figure 7.13 result in these respective access sequences. A preorder traversal is also called a * depth-first* traversal.

It should now be clear that confining attention to binary trees, their representation, and operations on them is not actually a restriction. That is, since trees can be represented as binary trees, any operations can be performed on them by performing equivalent operations on their binary tree representations. In this sense no generality is lost in dealing with binary trees.

In order to do this we must be able to traverse a general tree. As it is traversed, we can generate the binary tree by properly processing each node as it is accessed. A nonrecursive algorithm to preorder traverse a tree t follows.

Nonrecursive Tree Preorder Traversal

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

For each successor pointer ps of node.p,

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

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.

One last detail remains. In order to do the processing required on node.p and node.pb, process will be invoked. As already noted, process must create a sublist consisting of new nodes corresponding to the successors of node.p in t, set leftptr.pb to point to that sublist, and copy info.p into info.pb. We assume that a procedure create, given p, creates the required sublist, and returns with first pointing to the first node of that sublist. The preorder traversal algorithm to create the binary tree corresponding to a general tree is as follows:

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

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

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

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

Each node of t corresponds to a node of bt,

To generate a binary tree corresponding to an ordered tree:

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

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

In the last section a tree traversal was developed and used to generate a binary tree. Here and in the following two sections we will develop a modified tree traversal that employs backtracking. *Backtracking* is a useful technique in solving many problems. First we apply it to the *n*-queens problem.

To the right, or left, along its row

Up, or down, along its d1 diagonal

Up, or down, along its d2 diagonal

Since a queen can be moved along one of its rows, columns, or diagonals, a solution clearly is achieved by specifying how to place the *n* queens so that *exactly* one queen appears in each row and column, and no more than one queen appears on any diagonal of the board. One could attempt to find a solution by searching through all possible placements of the *n* queens satisfying these restrictions. There are, however, *n*! such placements. Even for a moderate *n*, this is obviously not a practical solution. Instead we must construct a solution. The idea behind the construction is to determine if the placements obtained for the first *i* queens can lead to a solution. If they cannot, abandon that construction and try another, since placing the remaining *n* - *i* queens will not be fruitful. This *may* avoid the need to consider all possible constructions.

Suppose a path has been found to a node at depth *k*. The path is *feasible* if none of the *k* queens whose positions are specified by the path can take any other. If the node at depth *k* is a terminal node, and the path is feasible, then a solution has been found and may be printed. If the node at depth *k* is not terminal, and the path is feasible, we want to extend the path to a node at depth *k* + 1. Let p point to such a node. Then node.p must be a successor of the node on the path at depth *k*.

P *is feasible* if the position that node. p specifies for the (*k* + 1)th queen does not allow it to take any of the other *k* queens. If p is feasible, the path can be extended downward in the tree to include node.p, so there is now a feasible path of depth *k* + 1. If p is *not* feasible, then another successor of the node at depth *k* must be tried until a feasible one is found to extend the path, or until all have been tried and none is feasible. In the latter case, the choice of node at depth *k* cannot be extended to a solution, and the computer backs up in the tree to a node representing a shorter path that has not yet been explored. This procedure to extend the new path is repeated until a solution is found or until all possibilities have been tried.

The procedure described amounts to a modified general tree traversal called * backtracking*. A different approach would be to create an algorithm for the problem by applying a general tree preorder traversal that uses a process routine. The process routine would check each node to be processed to see whether the node is terminal and represents a feasible path. If so, it prints the solution. This approach amounts to an exhaustive search of all

A backtracking algorithm can be derived by modifying the general tree preorder traversal algorithm. The "p not null" test in the loop body of the preorder traversal algorithm must be replaced by two tests. One to see if p points to an existing node and another "p feasible" test to prune the tree. How this feasibility test is implemented is what determines the amount of pruning that occurs and hence the efficiency of the solution. The process routine called in the loop body must determine if node.p is terminal, and, if so, print the solution. If these were the only changes made, then nothing at all would be printed when no solution exists.

Backtracking Preorder Tree Traversal

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

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

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

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

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

If node.p is a terminal node, then

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

The nonrecursive solution may be written as follows.

# 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 i^{th}

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;

3r, d1,andd2will contain the board configuration

diagonalcheck1 d1;

diagonalcheck2 d2;

col = 1;

2colandrowdetermine 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 *n*4. For the curious, the number of solutions for *n* up to 15 are:

N4 5 6 7 8 9 10

Solutions 2 10 4 40 92 352 724

N11 12 13 14 15

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

One final point about the backtracking traversal algorithm. Suppose the **while** loop task is replaced by the task:

push all successors of node.p onto the stack

There is another type of modified tree traversal which is often found useful. It is called a * branch and bound traversal.* An algorithm for this traversal is as follows:

Nonrecursive Branch and Bound Traversal

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

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

This algorithm uses a data abstraction consisting of a bag data structure and operations on the bag that set it to empty, test it for emptiness, select (and remove) a pointer from it, and add a pointer to it. The idea is to define the select operation so that it removes the pointer from the bag that points to the node most likely to lead to a solution. The execution time required by the branch and bound traversal is directly related to how well the select function does the job of picking the next node to process and how well the feasible function does its job of pruning the tree. The better the selection and pruning the better the execution time. The select function should return null if the bag is empty.

If the select function always selects the node most recently added to the bag, then the data abstraction becomes a stack, and the algorithm is turned into a backtracking depth-first traversal. If the select function always selects the node that was added earliest to the bag, then the data abstraction becomes a queue, and the algorithm is turned into a backtracking breadth-first traversal. Thus backtracking may be viewed as a special case of branch and bound.

Horowitz and Sakni [1978] contains extensive discussions of backtracking and branch and bound traversals, with many applications worked out in detail. Also see Golomb and Baumert [1965]. Wirth [1976] deals with these techniques for problem solving; in particular, the stable marriage problem and the eight-queens problems are solved recursively.

Now that we are steeped in trees, we can look back at Figures 4.2 and 4.4 and notice that they are pictures of trees. We shall call them the *execution trees* of their corresponding recursive programs. In fact, any recursive program can be viewed as generating such a tree as it executes. The recursive program can be thought of as executing by traversing its corresponding execution tree. The processing done at each node in the course of this traversal is the carrying out of the program's task on a specific problem specified by its data and current scratchpad. Now that you know a good deal about tree traversals, is it any wonder that the stack appears in the translation of a recursive program? It is clearly the number of nodes in the tree that determines the execution time of the algorithm, and it is the depth of the tree that determines the storage requirements. This point can become somewhat muddled when recursion is applied to trees themselves, but you should realize that this is the case even when no trees are apparent in the nature of the problem, as in the Towers of Hanoi problem in Chapter 4.

In a* balanced* binary tree, no matter what node of the tree is considered, the left and right subtrees of that node have depths that differ by at most 1.

A binary tree is a * Fibonacci tree* if it is balanced and has the minimum number of nodes among all balanced binary trees with its depth. Fibonacci trees represent the worst case for balanced trees, since they contain the fewest nodes (and hence the least storage capacity) among all balanced trees with a specified depth. The binary tree in Figure 7.19 is a Fibonacci tree of depth 4. This is a Fibonacci tree because it is balanced, and no balanced binary tree with a depth of 4 has fewer than 7 nodes. Any complete binary tree of depth 4, for example, will not be a Fibonacci tree because, although balanced, it will have more than the minimum number of nodes (7) for this depth.

F_{0}= 0,F_{1}= 1,

F=_{n}F-1 +_{n}F-2 for_{n}n> 1

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,

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 recursive program can be written directly from the definition.

Recursive Version 1--Linked Representation with Records Stored in an Array

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.

Recursive Version 2--Linked Representation with Records Stored in Dynamic Memory

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);

}

}

Consider the execution tree for these functions when *d* = 6, which is given in Figure 7.20. Each node of the tree represents a call to the recursive function Fibonaccitree. Nodes with the same *d*-value thus correspond to requests of the recursive function to carry out identical tasks, that is, to create identical trees.

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

The number of nodes in a Fibonacci tree of depth d is *F _{d}*+2 - 1.

* In fact, the number of nodes will be 2*F _{d}*+1 - 1.

An Efficient Nonrecursive Version

b. set t to point to the root node;

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

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.

I think that I shall never see

Indeed, unless the billboards fall

**1. a. **What is the minimum number of nodes that a binary tree of depth *d* can have?

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

**2.** Suppose t is a binary tree with *n* internal nodes and *m* terminal nodes. **T** is a* full binary tree* if each of its nodes has zero or two successors. What is the relation between

**3.** There are 0, 1, 2, and 5 distinct binary trees with, respectively, 0, 1, 2, and 3 nodes.

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

**4.** Modify the program segments of Section 7.2.1 so that they work correctly in all cases.

**5.** **a**. Suppose the binary tree that follows is preorder, inorder, and postorder traversed. List the order in which the nodes will be accessed for each.

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

**6.** Prove that all terminal nodes will always be accessed in the same relative order for all three travelsals.

**7. a. **Suppose the stack used in a pre-, in-, or postorder traversal is implemented as an array. What is the requirement for limit in terms of the depth of the binary tree, to guarantee that the stack is large enough for the traversal to work?

**8.** Suppose the following two binary trees are preorder and postorder traversed. The preorder and postorder listings are given for each tree.

**9. a. **Can you find a way to use the left and right pointer fields of terminal and internal nodes that contain null pointers in a binary tree to create "threaded binary trees" so that they can be traversed without using a stack? (*Hint*: Consider pointers that point to the predecessor and successor of a terminal node in an inorder traversal.)

**b. **What about for inorder and postorder traversals?

**10.** Write inorder and postorder traversal routines (nonrecursive and recursive).

**11. a. **Suppose you wish to use a linked representation for binary trees with an array implementation as in Figure 7.10. Suppose tht input is given as a name value followed by a sequence of records, each record representing a node of a binary tree. For the binary tree fred of Figure 7.10, the input would be

5

8 L 0

-1 O -1

3 U 4

-1 S -1

-1 T -1

**12. **The binary tree sample is stored using a linked representation. List the order in which its nodes will be accessed in a preorder 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

**13. **What will be in the stack during a preorder traversal of sample in Exercise 12 when its rightmost node is accessed? What about when it is inorder and postorder traversed?

**14. a. **Suppose every subtree of sample of Exercise 12 is interchanged with its right subtree. What will leftptr, info, and rightptr look like?

**15.** Suppose a binary tree is stored using the records array implementation as in Figure 7.10. If tree points to its root node, write a function to print out the sequence of pointers that specify the path in the tree to the right most node in tree. For example, in Figure 7.10 the rightmost node of fred is 1, and the sequence of pointers to be printed out for fred would be 6, 1, 5.

**16. a.** If the binary tree of Figure 7.5 were represented sequentially, what numbers would be assigned to its nodes?

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

**17.** When dealing with *arbitrary* binary trees, would you use linked or sequential representation? Why?

**18. a. **Write a function that will return, given a binary tree t, with a pointer to a terminal node of t containing the largest value in its information field.

**19.** Consider the binary tree that was produced by the transformation from a general tree to a binary tree as a general tree, and find the binary tree produced by its transformation.

**20.** Consider again the solution to the information retrieval problem of Chapter 6. Suppose you create a record, r, in memory. R will have a pointer field pointing to the record for a father. You can then think of r as a record representing the node of a binary tree.

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

**21. a. **Write a function to append a binary tree t1 to a binary tree t2 by replacing some terminal node in t2 at least depth by the whole tree t1. For example, see the figure. Use a linked representation with pointer variables.

**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?

**22. a**. Write a routine that deletes all the terminal nodes of a binary tree.

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

**23. a**. Write a function to interchange all left and right subtrees of a binary tree.

**24. a. **Modify the preorder traversal so that it returns, in a variable identical, a value *true* if t1 and t2 point to identical trees, and a value *false* otherwise. That is, the value is *true* if the two trees have the same structure and the same information field values.

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

**25. a.** Suppose you are given a maze with the structure of a binary tree. The maze has a starting point and an exit. A node is associated with the starting point, with the exit, and with every point in the maze where one of two paths must be taken. The maze is given as a two-dimensional array a. A [i,j] is 1 if there is a path from node i to node j in the maze, and is 0 otherwise. There are *n* points in the maze. Adapt the preorder traversal to achieve an algorithm for solving the maze--that is, for printing out the path from the starting node to the exit node. Your solution should be detailed enough to write a function corresponding to it directly.

**26. a. **Modify the preorder traversal algorithm for creating a binary tree from a general tree (p. 332) and the process algorithm so the preorder traversal returns, in the variable transform, a value "true" only if a binary tree bt is the transformed version of a general tree t.

**27.** Write the function create used in the process algorithm.

**28.** Modify the backtracking preorder traversal algorithm so that it does a backtracking* breadth-first* traversal.

**29.** Suppose you are given a "map" of *n* cities and the distances between them. Can you find a way to modify the preorder traversal algorithm to determine the shortest distance between two cities? What is a feasible test to use to allow feasible to limit the execution time of the solution?

**30. a. **Suppose a general tree is given as follows:

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

This corresponds to the general tree:

**31. ***T *is a binary tree.* *Result(t)* *is defined by

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)*?*

**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(0) = 1

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

+b(n- 1) xb(0)n> 0

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

**34. a. **Give a recursive definition of balanced binary trees.

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

**35.** Write a recursive function result corresponding to Exercise 31.

**36. a. **Write a recursive function count to return the number of terminal nodes of a binary tree.

**37. **Write a recursive routine partialexchange to interchange all subtrees of a binary tree whose left subtree info field value exceeds the right subtree value. Assume the binary tree is represented using pointer variables.

**38.** Write a recursive function using pointers to transform a general tree into its binary tree representation.

**39.** Write a recursive program that produces a solution, if one exists, to the *n*-queens problem.

**40.** Write a recursive function to produce a copy of a binary tree. Both trees should be implemented using pointers.

**1. **Write a function to print the family tree for an individual whose family history is stored in the data base of the case study of Chapter 6. The individual is at the root of the family tree, and its subtrees are the family trees of all the individual's children. Print the tree using indentation as in Figure 7.1(a). Assume individual records are stored in dynamic memory and that the appropriate functions are available for searching and accessing the nametables. If this function is to also be executed, then this would be a good assignment for a group project.

**2. **Consider the problem of finding a stable pairing, given preferences, as discussed in Chapter 2. Describe a tree that represents all possible pairings, and write a backtracking traversal function to produce all stable pairings. Base your solution on the backtracking preorder traversal algorithm given in the text. Compare this solution with the solution given in Chapter 2.

**3. **Formulate a solution to the stable pairing problem as a traversal through all permutations of the men. Use the permutation traversal program of Chapter 4 as the basis for your algorithm. Compare this solution to your solution to Assignment 2 and also to the solution given in Chapter 2.

**4. **Write an efficient recursive function fibonaccicheck(t,d,flag), which is to return in d the depth of the binary tree t, and with flag *true* if t is a Fibonacci tree and *false *otherwise.