In this chapter we shall study a very important data object, trees. Intuitively, a tree structure means that the data is organized so that items of information are related by branches. One very common place where such a structure arises is in the investigation of genealogies. There are two types of genealogical charts which are used to present such data: the *pedigree* and the *lineal* chart. Figure 5.1 gives an example of each.

With these two examples as motivation let us define formally what we mean by a tree.

A *forest* is a set of *n* 0 disjoint trees. The notion of a forest is very close to that of a tree because if we remove the root of a tree we get a forest. For example, in figure 5.2 if we remove *A* we get a forest with three trees.

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

The information in the root node comes first followed by a list of the subtrees of that node.

Now, how do we represent a tree in memory? If we wish to use linked lists, then a node must have a varying number of fields depending upon the number of branches.

_____________________________________

| | | | | |

|DATA |LINK 1 |LINK 2| |LINK n |

|______|________|______|______|_______|

A binary tree is an important type of tree structure which occurs very often. It is characterized by the fact that any node can have at most two branches, i.e., there is no node with degree greater than two. For binary trees we distinguish between the subtree on the left and on the right, whereas for trees the order of the subtrees was irrelevant. Also a binary tree may have zero nodes. Thus a binary tree is really a different object than a tree.

structureBTREE

declareCREATE( )btree

ISMTBT(btree)boolean

MAKEBT(btree,item,btree)btree

LCHILD(btree)btree

DATA(btree)item

RCHILD(btree)btree

for allp,rbtree, ditemlet

ISMTBT(CREATE) :: =true

ISMTBT(MAKEBT(p,d,r)) :: =false

LCHILD(MAKEBT(p,d,r)):: =p;LCHILD(CREATE):: =error

DATA(MAKEBT(p,d,r)) :: =d;DATA(CREATE) :: =error

RCHILD(MAKEBT(p,d,r)) :: =r;RCHILD(CREATE) :: =error

end

endBTREE

This set of axioms defines only a minimal set of operations on binary trees. Other operations can usually be built in terms of these. See exercise 35 for an example.

Figure 5.3 shows two sample binary trees. These two trees are special kinds of binary trees. The first is a *skewed* tree, skewed to the left and there is a corresponding one which skews to the right. Tree 5.3b is called a *complete* binary tree. This kind of binary tree will be defined formally later on. Notice that all terminal nodes are on adjacent levels. The terms that we introduced for trees such as: degree, level, height, leaf, parent, and child all apply to binary trees in the natural way. Before examining data representations for binary trees, let us first make some relevant observations regarding such trees. First, what is the maximum number of nodes in a binary tree of depth *k*?

(i) The maximum number of nodes on level *i* of a binary tree is 2* ^{i}*-1,

(ii) The maximum number of nodes in a binary tree of depth *k* is 2* ^{k}* - 1,

(i) The proof is by induction on *i*.

**Induction Hypothesis:** For all *j*, 1 *j* < *i*, the maximum number of nodes on level *j* is 2* ^{j}* - 1.

(ii) The maximum number of nodes in a binary tree of depth *k* is (maximum number of nodes on level *i*)

**Lemma 5.2:** For any nonempty binary tree, *T*, if *n _{o}* is the number of ter minal nodes and

Subtracting (5.2) from (5.1) and rearranging terms we get

In Figure 5.3(a) *n _{0}* = 1 and

As we continue our discussion of binary trees, we shall derive some other interesting properties.

A *full* binary tree of depth *k* is a binary tree of depth *k* having 2* ^{k}* - 1 nodes. By Lemma 5.1, this is the maximum number of nodes such a binary tree can have. Figure 5.4 shows a full binary tree of depth 4. A very elegant sequential representation for such binary trees results rom sequentially numbering the nodes, starting with nodes on level 1, then those on level 2 and so on. Nodes on any level are numbered from left to right (see figure 5.4). This numbering scheme gives us the definition of a complete binary tree. A binary tree with

**Lemma 5.3:** If a complete binary tree with n nodes (i.e., depth= [log_{2}*n*] + 1) is represented sequentially as above then for any node with index *i*, 1 *i* *n* we have:

(i) PARENT(*i*) is at [*i*/2] if *i* 1. When *i* = 1, *i* is the root and has no parent.

(ii) LCHILD(*i*) is at 2*i* if 2*i* *n*. If 2*i* > *n*, then *i* has no left child.

(iii) RCHILD(*i*) is at 2*i* + 1 if 2*i* + 1 *n*. If 2*i* + 1 > *n*, then *i* has no right child.

TREE TREE

----- -----

(1) | A | | A |

|-----| |-----|

(2) | B | | B |

|-----| |-----|

(3) | - | | C |

|-----| |-----|

(4) | C | | D |

|-----| |-----|

(5) | - | | E |

|-----| |-----|

(6) | - | | F |

|-----| |-----|

(7) | - | | G |

|-----| |-----|

(8) | D | | H |

|-----| |-----|

(9) | - | | I |

|-----| -----

. | . |

|-----|

. | . |

|-----|

. | . |

|-----|

(16) | E |

-----

There are many operations that we often want to perform on trees. One notion that arises frequently is the idea of traversing a tree or visiting each node in the tree exactly once. A full traversal produces a linear order for the information in a tree. This linear order may be familiar and useful. When traversing a binary tree we want to treat each node and its subtrees in the same fashion. If we let *L, D, R* stand for moving left, printing the data, and moving right when at a node then there are six possible combinations of traversal: *LDR, LRD, DLR, DRL, RDL,* and *RLD*. If we adopt the convention that we traverse left before right then only three traversals remain: *LDR, LRD* and *DLR*. To these we assign the names inorder, postorder and preorder because there is a natural correspondence between these traversals and producing the infix, postfix and prefix forms of an expression. Consider the binary tree of figure 5.7. This tree contains an arithmetic expression with binary operators: add(+), multiply(*), divide(/), exponentiation(**) and variables *A, B, C, D*, and *E*. We will not worry for now how this binary tree was formed, but assume that it is available. We will define three types of traversals and show the results for this tree.

procedureINORDER(T)

//Tis a binary tree where each node has three fieldsL-

CHILD,DATA,RCHILD//

ifT0then[callINORDER(LCHILD(T))

DATA(T))

call(INORDER(RCHILD(T))]

endINORDER

Call of value

INORDER in root Action

------- ------- ----------

MAIN +

1 *

2 /

3 A

4 0 print('A')

4 0 print('/')

3 **

4 B

5 0 print('B')

5 0 print('**')

4 C

5 0 print('C')

5 0 print('*')

2 D

3 0 print('D')

3 0 print('+')

1 E

2 0 print('E')

2 0

The elements get printed in the order

which is the *in*fix form of the expression.

A second form of traversal is *preorder*:

procedurePREORDER(T)

//Tis a binary tree where each node has three fieldsL-

CHILD,DATA,RCHILD//

ifT0then[DATA(T))

callPREORDER(LCHILD(T))

callPREORDER(RCHILD(T))]]

endPREORDER

which we recognize as the *pre*fix form of the expression.

At this point it should be easy to guess the next traversal method which is called *postorder*:

procedurePOSTORDER(T)

//Tis a binary tree where each node has three fieldsL-

CHILD,DATA,RCHILD//

ifT0then[callPOSTORDER(LCHILD(T))

callPOSTORDER(RCHILD(T))

DATA(T))]

endPOSTORDER

The output produced by POSTORDER is

which is the postfix form of our expression.

Though we have written these three algorithms using recursion, it is very easy to produce an equivalent nonrecursive procedure. Let us take inorder as an example. To simulate the recursion we need a stack which will hold pairs of values (*pointer, returnad*) where *pointer* points to a node in the tree and *returnad* to the place where the algorithm should resume after an end is encountered. We replace every recursive call by a mechanism which places the new pair (*pointer, returnad*) onto the stack and goes to the beginning; and where there is a return or end we insert code which deletes the top pair from the stack if possible and either ends or branches to *returnad* (see section 4.10 for the exact details).

procedureINORDER1(T)

//a nonrecursive version using a stack of sizen//

i 0 //initialize the stack//

L1:ifT0then[ii+ 2;ifi>nthen callSTACK_FULL

STACK(i- 1)T; STACK(i) 'L2'

TLCHILD(T);go toL1; //traverse left

subtree//

L2:DATA(T))

ii+ 2;ifi>nthen callSTACK--FULL

STACK(i- 1)T; STACK(i) 'L3'

TRCHILD(T);go toL1] //traverse right

subtree//

L3:ifi0then[//stack not empty, simulate a return//

TSTACK(i- 1);XSTACK(i)

ii- 2;go toX]

endINORDER1

procedureINORDER 2(T)

//a simplified, nonrecursive version using a stack of sizen//

i0 //initialize stack//

L1:ifT0[thenii+ 1;ifi>nthen callSTACK__FULL

STACK(i)T; TLCHILD(T);go toL1

L2:DATA(T))

TRCHILD(T);go toL1]

ifi0then[//stack not empty//

TSTACK (i):ii- 1;go toL2]

endINORDER2

procedureINORDER3(T)

//a nonrecursive, nogo toversion using a stack of sizen//

i0 //initialize stack//

loop

whileT0do//move downLCHILDfields//

ii+ 1;ifi >nthen callSTACK--FULL

STACK(i)T; TLCHILD(T)

end

ifi= 0then return

TSTACK(i);ii- 1

DATA(T));TRCHILD(T)

forever

endINORDER3

2*n*_{0} + *n*_{1} = *n*_{0} + *n*_{1} + *n*_{2} + 1 = *n* + 1.

procedureCOPY(T)

//for a binary treeT, COPYreturns a pointer to an exact copy of

T; new nodes are gotten using the usual mechanism//

Q0

ifT0then[RCOPY(LCHILD(T)) //copy left subtree//

SCOPY(RCHILD(T)) //copy right subtree//

callGETNODE(Q)

LCHILD(Q)R;RCHILD(Q)S

//store in fields ofQ//

DATA(Q)DATA(T)]

return(Q) //copy is a function//

endCOPY

procedureEQUAL(S,T)

//This procedure has valuefalseif the binary treesSandTare not

equivalent. Otherwise, its value istrue//

ansfalse

case

:S= 0andT= 0:anstrue

:S0andT0:

ifDATA(S) =DATA(T)

then[ansEQUAL(LCHILD(S),LCHILD(T))

ifansthenansEQUAL(RCHILD(S),RCHILD(T))]

end

return(ans)

endEQUAL

As a second example of the usefulness of binary trees, consider the set of formulas one can construct by taking variables *x*_{1},*x*_{2},*x*_{3}, ... and the operators (and), (or) and (not). These variables can only hold one of two possible values, true or false. The set of expressions which can be formed using these variables and operators is defined by the rules: (i) a variable is an expression, (ii) if *x,y* are expressions then *x * y, x * y,* *x* are expressions. Parentheses can be used to alter the normal order of evaluation which is **not** before **and** before **or**. This comprises the formulas in the *propositional calculus* (other operations such as implication can be expressed using , , ). The expression

false (true false)

= false true

= true

The *satisfiability problem* for formulas of the propositional calculus asks if there is an assignment of values to the variables which causes the value of the expression to be true. This problem is of great historical interest in computer science. It was originally used by Newell, Shaw and Simon in the late 1950's to show the viability of heuristic programming (the Logic Theorist).

Again, let us assume that our formula is already in a binary tree, say

(*x*_{1 } *x*_{2}) ( *x*_{1}* * x_{3}) * *x_{3}

For the purposes of this algorithm we assume each node has four fields:

_____________________________

| | | | |

|LCHILD | DATA | VAL | RCHILD |

|_______|______|_____|________|

forall2^{n}possible combinationsdo

generate the next combination;

store it in DEF(1)to DEF(n);

callPOSTORDERand evaluate T;

ifVAL(T) =true then[DEF(1)to DEF(n)

stop]

end

no satisfiable combination')

procedurePOSTORDER_EVAL(T)

//a binary treeTcontaining a propositional formula is evaluated with

the result stored in theVALfield of each node//

ifT0then[callPOSTORDER_EVAL(LCHILD(T))

callPOSTORDER_EVAL(RCHILD(T))

case

:DATA(T) = ' :VAL(T)notVAL(RCHILD(T))

:DATA(T) = ' :VAL(T)VAL(LCHILD(T)or

VAL(RCHILD(T))

:DATA(T) = ' :VAL(T)VAL(LCHILD(T)and

VAL(RCHILD(T))

:else:VAL(T)DEF(DATA(T))

end]

endPOSTORDER_EVAL

If we look carefully at the linked representation of any binary tree, we notice that there are more null links than actual pointers. As we saw before, there are *n* + 1 null links and 2*n* total links. A clever way to make use of these null links has been devised by A. J. Perlis and C. Thornton. Their idea is to replace the null links by pointers, called threads, to other nodes in the tree. If the RCHILD(*P*) is normally equal to zero, we will replace it *by a pointer to the node which would be printed after P when traversing the tree in inorder*. A null LCHILD link at node *P* is replaced *by a pointer to the node which immediately precedes node P in inorder*. Figure 5.10 shows the binary tree of figure 5.3(b) with its new threads drawn in as dotted lines.

LBIT(P) =1 if LCHILD(P) is a normal pointer

LBIT(P) = 0 if LCHILD(P) is a thread

RBIT(P) = 1 if RCHILD(P) is a normal pointer

RBIT(P) = 0 if RCHILD(P) is a thread

procedureINSUC(X)

//find the inorder succcesor ofXin a threaded binary tree//

SRCHILD(X) //ifRBIT(X) = 0 we are done//

ifRBIT(X) = 1then[whileLBIT(S) = 1do//follow left//

SLCHILD(S)//until a thread//

end]

return(S)

endINSUC

procedureTINORDER(T)

//traverse the threaded binary tree,T, in inorder//

HEADT

loop

TINSUC(T)

ifT=HEADthen return

DATA(T))

forever

endTINORDER

We have seen how to use the threads of a threaded binary tree for inorder traversal. These threads also simplify the algorithms for preorder and postorder traversal. Before closing this section let us see how to make insertions into a threaded tree. This will give us a procedure for growing threaded trees. We shall study only the case of inserting a node *T* as the right child of a node *S.* The case of insertion of a left child is given as an exercise. If *S* has an empty right subtree, then the insertion is simple and diagrammed in figure 5.12(a). If the right subtree of *S* is non-empty, then this right subtree is made the right subtree of *T* after insertion. When this is done, *T* becomes the inorder predecessor of a node which has a LBIT = 0 and consequently there is a thread which has to be updated to point to *T.* The node containing this thread was previously the inorder successor of *S.* Figure 5.12(b) illustrates the insertion for this case. In both cases *S* is the inorder predecessor of *T.* The details are spelled out in algorithm INSERT_RIGHT.

procedureINSERT_RIGHT(S,T)

//insert nodeTas the right child ofSin a threaded binary tree//

RCHILD(T)RCHILD(S);RBIT(T)RBIT(S)

LCHILD(T)S;LBIT(T) 0 //LCHILD(T) is a thread//

RCHILD(S)T;RBIT(S) 1 //attach nodeTtoS//

ifRBIT(T) = 1then[WINSUC(T)//Shad a right child//

LCHILD(W)T]

endINSERT_RIGHT

**Lemma 5.4:** If *T* is a *k*-ary tree (i.e., a tree of degree *k*) with *n *nodes, each having a fixed size as in figure 5.13, then *n*(*k*- 1) + 1 of the *nk *link fields are zero, *n* 1.

___________________

| DATA |

|-------------------|

| CHILD | SIBLING |

|_________|_________|

This does not look like a binary tree, but if we tilt it roughly 45 clockwise we get

Let us try this transformation on some simple trees just to make sure we've got it.

One thing to notice is that the RCHILD of the root node of every resulting binary tree will be empty. This is because the root of the tree we are transforming has no siblings. On the other hand, if we have a forest then these can all be transformed into a single binary tree by first obtaining the binary tree representation of each of the trees in the forest and then linking all the binary trees together through the SIBLING field of the root nodes. For instance, the forest with three trees

We can define this transformation in a formal way as follows:

Preorder and inorder traversals of the corresponding binary tree *T *of a forest *F* have a natural correspondence with traversals on *F*. Preorder traversal of *T* is equivalent to visiting the nodes of *F* in *tree preorder* which is defined by:

(i) if *F* is empty then return;

(ii) visit the root of the first tree of** ***F;*

(iii) traverse the subtrees of the first tree in tree preorder;

(iv) traverse the remaining trees of *F* in tree preorder.

Inorder traversal of *T* is equivalent to visiting the nodes of *F* in *tree inorder* as defined by:

(i) if *F* is empty then return;

(ii) traverse the subtrees of the first tree in tree inorder;

(iii) visit the root of the first tree;

(iv) traverse the remaining trees in tree inorder.

The above definitions for forest traversal will be referred to as preorder and inorder. The proofs that preorder and inorder on the corresponding binary tree are the same as preorder and inorder on the forest are left as exercises. There is no natural analog for postorder traversal of the corresponding binary tree of a forest. Nevertheless, we can define the *postorder traversal of a forest *as*:*

(i) if *F* is empty then return;

(ii) traverse the subtrees of the first tree of *F* in tree postorder;

(iii) traverse the remaining trees of *F* in tree postorder;

(iv) visit the root of the first tree of *F*.

This traversal is used later on in section 5.8.3 for describing the minimax procedure.

In this section we study the use of trees in the representation of sets. We shall assume that the elements of the sets are the numbers 1, 2, 3, ..., *n*. These numbers might, in practice, be indices into a symbol table where the actual names of the elements are stored. We shall assume that the sets being represented are pairwise disjoint; i.e., if *S _{i} *and

(ii) Find(*i*) ... find the set containing element *i*. Thus, 4 is in set *S*_{3} and 9 is in set *S*_{1}.

procedureU(i,j)

//replace the disjoint sets with rootsiandj,ijwith their union//

PARENT(i)j

endU

procedureF(i)

//find the rootjof the tree containing elementi//

ji

whilePARENT(j) > 0do//PARENT(j) = 0 if this node is a

root//

jPARENT(j)

end

return(j)

endF

*U*(1,2), *F*(1), *U*(2,3), *F*(1),* U*(3,4)

*F*(1), *U*(4,5), ...,*F*(1), *U*(*n* - 1,*n*)

This sequence results in the degenerate tree:

procedureUNION(i,j)

//union sets with rootsiandj,ij, using the weighting rule.PARENT

(i) = -COUNT(i) andPARENT(j) = -COUNT(j)//

xPARENT(i) +PARENT(j)

ifPARENT(i) >PARENT(j)

then[PARENT(i)j//ihas fewer nodes//

PARENT(j) x]

else[PARENT(j)i//jhas fewer nodes//

PARENT(i)x]

endUNION

**Lemma 5.5: **Let *T* be a tree with *n* nodes created as a result of algorithm UNION. No node in *T* has level greater log_{2} *n* + 1.

Example 5.1 shows that the bound of Lemma 5.5 is achievable for some sequence of unions.

**Example 5.1:** Consider the behavior of algorithm UNION on the following sequence of unions starting from the initial configuration

PARENT(*i*) = -COUNT(*i*) = -1, 1 *i* *n* = 2^{3}

UNION(1,2), UNION(3,4), UNION(5,6), UNION(7,8),

UNION(1,3), UNION(5,7), UNION(1,5).

The following trees are obtained:

As is evident, the maximum level in any tree is log_{2} *m* + 1 if the tree has *m* nodes.

**Example 5.2: **: Consider the tree created by algorithm UNION on the sequence of unions of example 5.1. Now process the following 8 finds:

procedureFIND(i)

//find the root of the tree containing elementi. Use the collapsing

rule to collapse all nodes fromito the rootj//

ji

whilePARENT(j)>0do//find root//

jPARENT(j)

end

ki

whilekjido//collapse nodes fromto rootj//

tPARENT(k)

PARENT(k)j

kt

end

return(j)

endFIND

The worst case behavior of the UNION-FIND algorithms while processing a sequence of unions and finds is stated in Lemma 5.6. Before stating this lemma, let us introduce a very slowly growing function (*m,n*) which is related to a functional inverse of Ackermann's function *A*(*p,q*). We have the following definition for (*m,n*):

(*m,n*) = min{*z * 1 *A*(*z*,4*m*/*n*) > log_{2}*n*}

The definition of Ackermann's function used here is:

The function *A*(*p,q*) is a very rapidly growing function. One may prove the following three facts:

**Lemma 5.6:** [Tarjan] Let *T*(*m,n*) be the maximum time required to process any intermixed sequence of *m* *n* FINDs and *n* - 1 UNIONs. Then *k*_{1}*m* *(*m,n*)* * T*(*m,n*)* * k_{2}m* *(*m,n*) for some positive constants *k*_{1} and *k _{2}. *

In Chapter 6 we shall see another application of the UNION-FIND algorithms.

**Example 5.3:** We shall use the UNION-FIND algorithms to process the set of equivalence pairs of scction 4.6. Initially, there are 12 trees, one for each variable. PARENT(*i*)* = -*1, 1 *i ** 12*.

Another very useful application of trees is in decision making. Consider the well-known *eight coins* problem. Given coins *a,b,c,d,e,f,g,h,* we are told that one is a counterfeit and has a different weight than the others. We want to determine which coin it is, making use of an equal arm balance. We want to do so using a minimum number of comparisons and at the same time determine whether the false coin is heavier or lighter than the rest. The tree below represents a set of decisions by which we can get the answer to our problem. This is why it is called a decision tree. The use of capital *H* or *L* means that the counterfeit coin is *h*eavier or *l*ighter. Let us trace through one possible sequence. If *a + b + c < d + e + f*, then we know that the false coin is present among the six and is neither *g* nor *h*. If on our next measurement we find that *a + d < b + e*, then by interchanging *d* and *b* we have no change in the inequality. This tells us two things: (i) that *c* or *f* is not the culprit, and (ii) that *b* or *d* is also not the culprit. If *a + d* was equal to *b + e*, then *c* or *f* would be the counterfeit coin. Knowing at this point that either *a* or *e* is the counterfeit, we compare *a* with a good coin, say *b*. If *a = b*, then *e* is heavy, otherwise *a* must be light.

We will make use of a procedure to do the last comparison.

procedureCOMP(x,y,z)

//xis compared against the standard coinz//

ifx > zthen print(x'heavy')

else print(y'light')

endCOMP

Another interesting application of trees is in the playing of games such as tic-tac-toe, chess, nim, kalah, checkers, go, etc. As an example, let us consider the game of nim. This game is played by two players A and B. The game itself is described by a *board* which initially contains a pile of *n* toothpicks. The players *A* and *B* make moves alternately

procedureEIGHTCOINS

//eight weights are input; the different one is discovered using only

3 comparisons//

read(a, b, c, d, e, f, g, h)

case

:a+b+c=d+e+f:ifg>hthen callCOMP(g,h,a)

else callCOMP(h,g,a)

:a+b+c > d+e+f:case

:a+d=b+e:callCOMP(c,f,a)

:a+d>b+e:callCOMP(a,e,b)

:a+d<b+e:callCOMP(b,d,a)

end

:a+b+c<d+e+f:case

:a+d=b+e:callCOMP(f,c,a)

:a+d>b+e:callCOMP(d,b,a)

:a+d<b+e:callCOMP(e,a,b)

end

end

endEIGHTCOINS

A sequence *C*_{1}, ...,*C _{m}* of board configurations is said to be

(i) *C*_{1} is the starting configuration of the game;

(ii) *C _{i}, *0 <

The justification for (5.3) is fairly simple. If *x* is a square node, then it is at an odd level and it will be *A'*s turn to move from here if the game ever reaches this node. Since *A* wants to win he will move to that child node with maximum value. In case *x* is a circular node it must be on an even level and if the game ever reaches this node, then it will be *B'*s turn to move. Since *B* is out to win the game for himself, he will (barring mistakes) make a move that will minimize *A'*s chances of winning. In this case the next configuration will be {*V*(*c _{i}*)}. Equation (5.3) defines the

where *e*(*X*) = *E*(*X*) if *X* is a position from which A is to move and *e*(*X*) = - *E*(*X*) otherwise.

procedureVE(X,l)

//computeV'(X) by looking at mostlmoves ahead.e(X) is the

evaluation function for playerA. For convenience, it is assumed

that starting from any board configurationXthe legal moves of

the game permit a transition only to the configurationsC_{1},C_{2}, ...,C_{d}

ifXis not a terminal configuration.//

ifXisterminalorl= 0then returne(X)

ans-VE(C- 1 //traverse the first subtree//_{1},l

fori2toddo//traverse the remaining subtrees//

ansmax{ans, -VE(C,_{i}l- 1)}

end

return(ans)

endVE

Consider the game tree of figure 5.18. After *V*(*P*_{41}) has been computed, it is known that *V*(*P*_{33}) is at least *V*(*P*_{41})= 3. Next, when *V*(*P*_{55}) is determined to be 2, then we know that *V*(*P*_{42}) is at most 2. Since *P*_{33} is a max position, *V*(*P*_{42}) cannot affect *V*(*P*_{33}). Regardless of the values of the remaining children of *P*_{42}, the value of *P*_{33} is not determined by *V*(*P*_{42}) as *V*(*P*_{42}) cannot be more than *V*(*P*_{41}). This observation may be stated more formally as the following rule: The *alpha* value of a max position is defined to be the minimum possible value for that position. *If the value of a min position is determined to be less than or equal to the alpha value of its parent, then we may stop generation of the remaining children of this min position*. Termination of node generation under this rule is known as *alpha cutoff*. Once *V*(*P*_{41}) in figure 5.18 is determined, the alpha value of *P*_{33} becomes 3. *V*(*P*_{55}) alpha value of *P*_{33} implies that *P*_{56} need not be generated.

A corresponding rule may be defined for min positions. The *beta* value of a min position is the maximum possible value for that position. *If the value of a max position is determined to be greater than or equal to the beta value of its parent node, then we may stop generation of the remaining children of this max position*. Termination of node generation under this rule is called *beta cutoff*. In figure 5.18, once *V*(*P*_{35}) is determined, the beta value of *P*_{23} is known to be at most -. Generation of *P*_{57}, *P*_{58}, *P*_{59} gives *V*(*P*_{43}) = 0. Thus, *V*(*P*_{43}) is greater than or equal to the beta value of *P*_{23} and we may terminate the generation of the remaining children of *P*_{36}. The two rules stated above may be combined together to get what is known as *alpha-beta pruning*. When alpha-beta pruning is used on figure 5.18, the subtree with root *P*_{36} is not generated at all! This is because when the value of *P*_{23} is being determined the alpha value of *P*_{11} is 3. *V*(*P*_{35}) is less than the alpha value of *P*_{11} and so an alpha cutoff takes place. It should be emphasized that the alpha or beta value of a node is a dynamic quantity. Its value at any time during the game tree generation depends upon which nodes have so far been generated and evaluated.

procedureVEB(X,l,D)

//determineV'(X) as in eq. (5.4) using theB-rule and looking

onlylmoves ahead. Remaining assumptions and notation are

the same as for algorithmVE.//

ifX is terminalorl= 0then returne(x)

ans-. //current lower bound onV'(x)//

foriltoddo

ansmax{ans, -VEB(C,_{i}l-1,-ans)}

ifansDthen return(ans) //useB-rule//

end

return(ans)

endVEB

procedureAB(X,l,LB,D)

//same as algorithm VEB. LB is a lowerbound onV'(X)//

ifXis terminalorl= 0then returne(X)

ansLB//current lowerbound onV'(X)//

fori1toddo

ansmax{ans,-AB(C,_{i}l-1,-D,-ans)}

ifansDthen return(ans)

end

return(ans)

endAB.

One may easily verify that the initial call *AB*(*Y,l, *-,) gives the same result as the call *VE*(*Y,l*).

As a conclusion to our chapter on trees, we determine the number of distinct binary trees having *n* nodes. We know that if *n* = 0 or *n* = 1 there is one such tree. If *n* = 2, then there are two distinct binary trees

How many distinct binary trees are there with *n* nodes?

as the next approximation. Continuing in this way we arrive at the binary tree

As an example, consider the binary tree above with the following numbering of nodes:

Its preorder permutation is 1,2, ...,9 and its inorder permutation is 2,3,1,5,4,7,8,6,9.

1,2,3; 1,3,2; 2,1,3; 3,2,1; 3, 2, 1;

*M*_{1} * *M*_{2} * *M*_{3} * ... * *M _{n}*

(*M*_{1} * *M*_{2}) * *M*_{3} and *M*_{1} * (*M*_{2} * *M*_{3})

and if *n* = 4, there are five ways

((*M*_{1} * *M*_{2}) * *M*_{3}) * *M*_{4}, (*M*_{1} * (*M*_{2} * *M*_{3})) * *M*_{4},

*M*_{1} * ((*M*_{2 * }*M*_{3}) * *M*_{4})

(*M*_{1} * (*M*_{2} * (*M*_{3} * *M*_{4}))), ((*M*_{1} * *M*_{2}) * (*M*_{3} * *M*_{4}))

This formula and the previous one are essentially the same.

To obtain this number we must solve the recurrence of eq. (5.5). To begin we let

Using the formula to solve quadratics and the fact (eq. (5.5)) that *B*(0) = *b*_{0} = 1 we get:

Comparing eqs. (5.6) and (5.7)we see that *b _{n}* which is the coefficient of

Some simplification yields the more compact form

For other representations of trees see

For the use of trees in generating optimal compiled code see

Algorithm INORDER4 of the exercises is adapted from

Further tree traversal algorithms may be found in:

The use of threads in conneetion with binary trees is given in

For a further analysis of the set representation problem see

The computing time analysis of the UNION-FIND algorithms may be found in:

Our discussion of alpha-beta cutoffs is from

*Problem Solving Methods in Artificial Intelligence* by N. Nilsson, McGraw-Hill, New York, 1971.

**1. **For the binary tree below list the terminal nodes, the nonterminal nodes and the level of each node.

**2.** Draw the internal memory representation of the above binary tree using (a) sequential, (b) linked, and (c) threaded linked representations.

**3.** Write a procedure which reads in a tree represented as a list as in section 5.1 and creates its internal representation using nodes with 3 fields, TAG, DATA, LINK.

**4.** Write a procedure which reverses the above process and takes a pointer to a tree and prints out its list representation.

**5.** Write a nonrecursive version of procedure PREORDER.

**6.** Write a nonrecursive version of procedure POSTORDER without using **go to**'s**.**

**7.** Rework INORDER3 so it is as fast as possible. (Hint: minimize the stacking and the testing within the loop.)

**8.** Write a nonrecursive version of procedure POSTORDER using only a fixed amount of additional space. (See exercise 36 for details)

**9.** Do exercise 8 for the case of PREORDER.

**10.** Given a tree of names constructed as described in section 5.5 prove that an inorder traversal will always print the names in alphabetical order.

Exercises 11-13 assume a linked representation for a binary tree.

**11.** Write an algorithm to list the DATA fields of the nodes of a binary tree *T* by level. Within levels nodes are to be listed left to right.

**12.** Give an algorithm to count the number of leaf nodes in a binary tree *T*. What is its computing time?

**13.** Write an algorithm SWAPTREE(*T*) which takes a binary tree and swaps the left and right children of every node. For example, if *T* is the binary tree

**14.** Devise an external representation for formulas in the propositional calculus. Write a procedure which reads such a formula and creates a binary tree representation of it. How efficient is your procedure?

**15.** Procedure POSTORDER-EVAL must be able to distinguish between the symbols ,, and a pointer in the DATA field of a node. How should this be done?

**16.** What is the computing time for POSTORDER-EVAL? First determine the logical parameters.

**17.** Write an algorithm which inserts a new node *T* as the left child of node *S* in a threaded binary tree. The left pointer of *S* becomes the left pointer of *T*.

**18.** Write a procedure which traverses a threaded binary tree in postorder. What is the time and space requirements of your method?

**19.** Define the inverse transformation of the one which creates the associated binary tree from a forest. Are these transformations unique?

**20.** Prove that preorder traversal on trees and preorder traversal on the associated binary tree gives the same result.

**21.** Prove that inorder traversal for trees and inorder traversal on the associated binary tree give the same result.

**22.** Using the result of example 5. 3, draw the trees after processing the instruction UNION(12,10).

**23.** Consider the hypothetical game tree:

(a) Using the minimax technique (eq. (5.3)) obtain the value of the root node .

(b) What move should player *A* make?

(c) List the nodes of this game tree in the order in which their value is computed by algorithm *VE*.

(d) Using eq. (5.4) compute *V'* (*X*) for every node *X* in the tree.

**24.** Show that *V'*(*X*) computed by eq. (5.4) is the same as *V*(*X*) computed by eq. (5.3) for all nodes on levels from which *A* is to move. For all other nodes show that *V*(*X*) computed by eq. (5.3) is the negative of *V'*(*X*) computed by eq. (5.4).

**25.** Show that algorithm *AB* when initially called with *LB* = - and *D* = yields the same results as *VE* does for the same *X* and *l*.

**26.** Prove that every binary tree is uniquely defined by its preorder and inorder sequences .

**27.** Do the inorder and postorder sequences of a binary tree uniquely define the binary tree? Prove your answer.

**28.** Answer exercise 27 for preorder and postorder.

**29.** Write an algorithm to construct the binary tree with a given preorder and inorder sequence.

**30.** Do exercise 29 for inorder and postorder.

**32.** Using Stirling's formula derive the more accurate value of the number of binary trees with *n* nodes,

**33.** Consider threading a binary tree using preorder threads rather than inorder threads as in the text. Is it possible to traverse a binary tree in preorder without a stack using these threads?

**34.** Write an algorithm for traversing an inorder threaded binalry tree in preorder.

**35.** The operation PREORD(btree) queue returns a queue whose elements are the data items of btree in preorder. Using the operation APPENDQ(queue, queue) queue which concatenates two queues, PREORD can be axiomatized by

PREORD(CREATE) :: = MTQ

PREORD(MAKBT(p,d,r)) :: =

APPENDQ(APPENDQ(ADDQ(MTQ,d),(PREORD(p)),PREORD(r))

Devise similar axioms for INORDER AND POSTORDER.

**36.** The algorithm on page 281 performs an inorder traversal without using threads, a stack or a PARENT field. Verify that the algorithm is correct by running it on a variety of binary trees which cause every statement to execute at least once. Before attempting to study this algorithm be sure you understand MARK2 of section 4.10.

**37.** Extend the equivalence algorithm discussed in section 5.8.1 so it handles the equivalencing of arrays (see section 4.6). Analyze the computing time of your solution.

**38.** [Wilczynski] Following the conventions of LISP assume nodes with two fields . If *A* = ((*a*(*bc*))) then HEAD(*A*) = (*a*(*bc*)), TAIL(A) = NIL, HEAD(HEAD(*A*)) = *a*, TAIL(HEAD(*A*))* =* ((*bc*)). CONS(*A,B*) gets a new node *T*, stores *A* in its HEAD, *B* in its TAIL and returns *T*. *B* must always be a list. If *L = a, M = *(*bc*) then CONS(*L,M*)* = *(*abc*), CONS(*M,M*) = ((*bc*)*bc*). Three other useful functions are: ATOM(*X*) which is true if *X* is an atom else false, NULL(*X*) which is true if *X* is NIL else false, EQUAL(*X,Y*) which is true if *X* and *Y* are the same atoms or equivalent lists else false.

b) Write recursive procedures for: COPY, REVERSE, APPEND.

line procedureINORDER4(T)

//inorder traversal of binary treeTusing a fixed amount of

additional storage//

1ifT= 0then return//empty binary tree//

2toplast_right0;pqT//initialize//

3loop

4loop//move down as far as possible//

5case

6:LCHILD(p)=0 andRCHILD(p)=0:

//can't move down//

7DATA(p));exit

8 :LCHILD(p) = 0: //move toRCHILD(p)//

9DATA(p))//visitp//

10rRCHILD(p);RCHILD(p)q;

qp;pr

11 :else: //move toLCHILD(p)//

12rLCHILD(p);LCHILD(p) q; qp;

pr

13end

14forever

//pis a leaf node, move upwards to a node whose right

subtree hasn't yet been examined//

15avp//leaf node to be used in stack//

16loop//move up fromp//

17case

18 :p = T:return//can't move up from root//

19 :LCHILD(q)=0://qis linked viaRCHILD//

20rRCHILD(q); RCHILD(q)p; pq; qr

21 :RCHILD(q)=0://qis linked viaLCHILD//

22rLCHILD(q); LCHILD(q)p; pq; qr;

DATA(p))

23 :else: //check ifpisRCHILDofq//

24ifq = last_rightthen[//pisRCHILDofq//

25 rtop; last_{}--rightLCHILD(r)//update

last_{}--right//

26topRCHILD(r); //unstack//

27 LCHILD(r)_{ }RCHILD(r)0//reset leaf

node links//

28rRCHILD(q);RCHILD(q)p; p_{ }q; qr]

29else[//p is LCHILDofq//

30DATA(q))//visitq//

31LCHILD(av)last_right; RCHILD(av)top;

topav

32last_rightq

33rLCHILD(q); LCHILD(q)p

//restore link top//

34r_{1 }_{ }RCHILD(q);RCHILD(q)r; pr_{1};exit

//move right//]

35end

36forever

37forever

38endINORDER4