INTRODUCTION:           

Having built a binary tree in the memory of your computer, we need the algorithms to verify that the tree is indeed ordered.  The recursive inorder algorithm is elegant, clean, but difficult to follow.  You must understand this algorithm, for it provides a template for many binary tree routines.  Once convinced that the tree is correct we will code a recursive search algorithm.

The key topics for this lesson are:

A.      Inorder Tree Traversal
B.      Preorder and Postorder Tree Traversals
C.      Counting the Nodes in a Tree
D.      Searching a Binary Tree

VOCABULARY:           

DISCUSSION:     

A.      Inorder Tree Traversal

2.      As a review, assume the following type definitions apply in this student outline.

struct treeNode

{

        int  data;

        treeNode  *left, *right;

        // struct constructor declaration

};

typedef treeNode*  treePtr;

3.      A tree traversal is an algorithm which visits every node in the tree.  To visit a node means to process something regarding the data stored in the node.  For now, visiting the node will involve printing the data field.

4.      An inorder tree traversal visits every node in a certain order.  Each node is processed in the following sequence:

Solve left subtree inorder

Visit node

Solve right subtree inorder

Notice that visiting the node is placed between the two recursive calls.

5.      Here is the code for function inorder:

void inorder (treePtr temp)

{

        if (temp != NULL)

        {

                inorder (temp->left);

                cout << temp->data << endl;

                inorder (temp->right);

        }

}

6.      The first call of inorder is asked to process the root node.  The first step of the function is a recursive call of inorder to process the left pointer of the root node.  This recursive call to solve the left pointer will take place before the cout statement.

7.      Solving for the node with value 14 results in another recursive call to solve the left pointer to the node having value 9.  The inorder to process the node with value 9 in turn calls inorder which hits a NULL.  This recursive call results in nothing executed.

8.      The recursion backtracks to the inorder processing the node with value 9.  Our first cout occurs and the value 9 is printed.  We recursively visit the node to the right and since nothing is there, we return to the node with value 9.

9.      For the node with value 9, we have now done all three steps.  We checked left, printed the 9, and checked right.  This function call is done and we backtrack to where we left off, which is processing the node with value 14. 

10.      From here, the recursion will continue working its way through the tree.  Inorder calls which are postponed are placed on the stack.  When a call of inorder is completed, the program will go to the stack (if necessary) to backtrack through the tree.

B.      Preorder and Postorder Tree Traversals

1.      A preorder tree traversal processes each node in a different order.

Visit the node

Process the left subtree preorder

Process the right subtree preorder

The only difference is that we will print first, then go left, then right.  The preorder output of the same binary tree will be:

26  14  9  21  79  53  35  99  87

2.      A postorder tree traversal has this order:

Process left subtree postorder

Process right subtree postorder

Visit the node

The prefix “post” refers to after, hence the location of visiting the node after the recursive calls.  The printout of the same tree will be as follows:

9   21   14   35   53   87   99   79   26

C.      Counting the Nodes in a Tree

1.      A standard binary tree algorithm is to count the number of nodes in the tree.  Here is a pseudocode version.

Count left subtree recursively

Count the current node as one

Count right subtree recursively

2.      As you develop the code, consider what base case will terminate the solution.

D.      Searching a Binary Tree

1.      Searching an ordered binary tree can be solved iteratively or recursively.  Here is the iterative version.

treePtr search (treePtr temp, int idToFind)

{

        treePtr back;

        while ((temp != NULL) && (idToFind != temp->data))

        {

                back = temp;

                if (idToFind < temp->data)

                        temp = temp->left;

                else

                        temp = temp->right;

        }

        return temp;

}

2.      If the value is not in the tree, the temp pointer will eventually hit a NULL.

3.      A recursive version is left for you to solve as part of the lab exercise.

4.      The order of searching an ordered binary tree is O(log2N) for the best case situation.  For a perfectly balanced tree, the capacity of each level is 2level #.

                Level #                Capacity of Level                Capacity of Tree

                0                1                1

                1                2                3

                2                4                7

                3                8                15

                4                16                31

                5                32                63

                etc.

5.      So starting at the root node, a tree of 63 nodes would require a maximum of 5 left or right moves to find a value.  The number of steps in searching an ordered binary tree is approximately O(log2N).

SUMMARY/REVIEW:            The most important topic of this lesson is recursive algorithms required to process binary trees.  Study the examples, draw pictures, do whatever it takes to understand recursive tree traversals.  Many of the algorithms in future lessons will require recursion.

ASSIGNMENT:           

Worksheet W.A.37.1, Recursive Tree Traversals

Lab Exercise L.A.37.1, BTree BTree (continued) Assignment:

1.   Continuing the lab exercise L.A.36.1, BTree,  from the previous lesson, add function inorder to print out the binary tree.  Format the output into two columns, Id and Inv amounts.

2.   Complete the search and countNode algorithms.