CS301 Data Structures Lecture No. 14

CS301 – Data Structures Lecture No. 14

______

Data Structures

Lecture No. 14

Reading Material

Data Structures and Algorithm Analysis in C++ Chapter. 4

4.3, 4.6

Summary

• Recursive Calls
• Preorder Recursion
• Inorder Recursion
• Non-Recursive Traversal
• Traversal Trace

We discussed the methods of traversal of the binary tree in the previous lecture. These methods are- preorder, inorder and postorder. It was witnessed that in the C++ code that the coding of these methods becomes very short with the use of recursive calls. The whole tree can be traversed with a few lines of code. We also demonstrated the benefits of the methods with the help of an example in which a tree was traversed by preorder, inorder and postorder methods. Implementation of the recursion also came under discussion in the previous lecture.

Recursive Calls

We know that function calls are made with the help of stacks. When a function calls some other function, the parameters and return address of the function is put in a stack. The local variables of the function are also located at the stack and the control is passed to the called function. When the called function starts execution, it performs its job by using these parameters and local variables. When there in the function there comes a return statement or when the function ends then the return address, already stored in the stack, is used and control goes back to the next statement after the calling function.Similarly when a function is calling to itself, there is no problem regarding the stack. We know, in recursion a function calls to itself instead of calling some other function. Thus the recursion is implemented in the way as other function calls are implemented.

Preorder Recursion

Now let’s see the preorder traversal with respect to the recursion. We will see what changes happen when preorder function calls itself recursively. Consider the following binary search tree used in our previous example.

For the preorder traversal, we call the preorder function and pass it the root node of the tree (i.e. 14) as a parameter. We have discussed in the preorder traversing that preorder method first prints the value of the node that is passed to it. So number 14 is printed. After it, the preorder method calls itself recursively. Thus we will call the preorder and give it the left subtree of 14 (actually the root node of left subtree) as an argument. So this call will be preorder (4). As it is preorder traversing, the value of the root node i.e. 4 will be printed. Now the preorder method looks if there is a left subtree of the node (i.e.4). If it has a left subtree,the preorder function will call itself again. The root node of this left subtree will be passed as an argument to the new function call. Here it is 3,so the number 3 is printed. Thus by the previous three calls (i.e. preorder(14), preorder(4) and preorder(3) ) we have printed the values 14, 4 and 3. Now the left subtree of 3 is NULL. We know that in preorder method, first of all we check whether the node is NULL or not. If it is not NULL, the recursion process continues. It means that we print the value of the node and call the preorder function again. If the node is NULL, the process ends.

There is always a terminating condition in recursive call or recursive procedure. In the previous lecture, while trying to end the factorial recursion, we defined the condition that the factorial of zero is 1. When the factorial of n starts, the factorial is called again and again by decreasing the value of n by 1. So when we reach at 0, there is no further recursive call for the factorial as we have set the condition for it i.e. the factorial of 0 is equal to 1. Thus the recursion ends. Equally is true about the preorder process. When a node is NULL, then ‘if statement’ becomes false and we exit the function (see code of preorder function in previous lecture).

In the above figure, the preorder process that started from node 14, came to an end at node 3 as the left subtree of 3 is NULL. Now this preorder process will make no further recursive call. We will come back from here by using the return address of the call preorder (NULL) from the stack. If we see the stack, this fourth call will come back to the third call i.e. preorder (3). The left subtree of 3 has ended. Now we have to traverse the right subtree of 3. Here the right subtree of 3 is also NULL. So the traversing of tree with node 3 as root has been completed. Now we return from the call preorder (3) and reach one level backward at the node 4. The left subtree of node 4 has been traversed. Now we go to traverse the right subtree of 4. The preorder call for the right subtree has started. This started from the call preorder (9).Note in the figure that this call has made at the same level as was for node 3. It is because we are traversing the right subtree of the same tree that has node 4 as its root and 3 was its left subtree. After printing the number 9 we go to call the preorder process for the left subtree of 9. That is preorder (7). When we go to 7, we print it and call the preorder process for its left subtree i.e. preorder (5). Now after printing the number 5, the preorder is applied to its left subtree i.e. NULL. So the preorder traversal of left subtree of 5 ends this way. Now the preorder is applied to the right subtree of 5 which is also NULL. Thus the next two preorder calls (one for left subtree of 5 and one for right subtree of 5) after the call preorder (5) are preorder (NULL). Here the returning address takes the control back to the call preorder (7) through the use of stack. The left subtree of 7 has been traversed and now we go to the right subtree of it i.e. NULL. Thus there is a call preorder (NULL). So we come back to node 9 completing the traversal of its left subtree. Now we traverse the right subtree of 9 which again happens to be NULL. So there is one more call of preorder with NULL. The number of dots with the preorder calls in the figure describes the state of the stack. When we go ahead to traverse a node the dots increase in figure as the call made is put on the stack. When we come back to a node, the returning address is popped from the stack and we mention it by decreasing a dot in the figure.

After these four calls of preorder with NULL as argument, we return to the node 4. We have completed the tree (left and right subtree ) with node 4 as root. As seen in the figure, this tree (having node 4 as root) is a left subtree of node 14. The numbers that we got printed upto now are 14, 4, 3, 9, 7 and 5. So after traversing the left subtree of 14, we come back to node 14 and start to traverse its right subtree. We traverse the right subtree by applying the recursive calls of preorder in the way as done while traversing the left subtree of 14. The recursive calls involved in it are shown in the following figure.

Now we are at node 14 and know that in preorder, the value of the node is printed first before going to its left subtree. And after traversing the left subtree, a programmer comes back and goes to traverse the right subtree. As we have traversed the left subtree of 14 and have come back to 14, now we will traverse the right subtree of 14. In the right subtree, we reach at node 15. We print the value 15 and look at its left subtree. The left subtree is NULL so the call to the preorder method is preorder (NULL). This call makes the condition of ‘if statement’ false and the recursive calls ends on this side. Afterwards, we go to the right subtree of 15. The call preorder (18) is made, followed by printing of the value 18. Then we go to the left subtree of it that is node 16. After calling preorder(16) and printing it, we go to the left subtree of 16 which is NULL. Now we will move to right subtree of 16 and the call preorder (17) prints the number 17. After it, the two next calls are preorder (NULL) as the left and right subtree of 17 are NULL. Thus after traversing the left and right subtree of 16 (which itself is a left subtree of 18), we return to node 18. Then we go to the right subtree of 18 and reach at node 20. So preorder (20) prints the value 20. There are again two preorder (NULL) calls as the left and right subtree of 20 are NULL. The preorder recursive call ends here. Now we go back and reach at node 14 whose left and right subtrees have been traversed. That means the whole tree having 14 as the root has traversed.

Inorder Recursion

Now let’s see the inorder recursive calls for traversing a tree. It is not different from the preorder. The pattern of recursive calls will be changed as in the inorder we traverse the left subtree first before printing the root. Afterwards, the right subtree is traversed. The following figures (Fig 14.2(a) and 14.2(b)) explains this phenomenon of inorder recursion by showing the recursive calls.

We start the inorder with the call inorder (14) as the root of the tree is 14. Now in the inorder traversing, a programmer has to traverse the left subtree before printing the value of the root node and then going to the right subtree. So the call to the left subtree of 14 i.e. inorder (4) will lead to the node 4. At the node 4, the same process of calling its left subtree, before printing its value, will be applied and we reach at node 3 that is the left subtree of 4. From the node 3, we go to its left subtree. This left subtree is NULL. Here in the inorder method, we have the same terminating condition as that seen in the preorder i.e. we will not make further recursive calls if there becomes a NULL node in the method call. We end the recursion at that node and come back. Now when we come back from the NULL left subtree of 3 this shows that we have visited the left subtree of 3. So the value of the node i.e. 3 is printed. Now we go to the right subtree of 3. Here the inorder call is inorder (NULL). This call will make theif statement, in the inorder method, false, leading to the end of the recursion. Thus we have visited the whole tree whose root is node 3. So we come back to node 4. As the left subtree of node 4 has been visited, we print the value of node i.e. 4. Thus we have printed the numbers 3 and 4. Now we go to the right subtree of 4. The right subtree of 4 is the node 9. Now we send 9 as an argument to inorder method. So there is a call inorder (9). As it is inorder traversing, we go to traverse its left subtree before printing the number 9. We reach the node 7 and make a call inorder (7). Later, we go to the left subtree of 7 i.e. the node 5. Now we visit the left subtree of 5 which is NULL. So here the inorder recursion ends and we come back to node 5, print it and go to the right subtree of 5. The right subtree of 5 is also NULL. So ending recursion here, we have finally traversed the tree with 5 as its root. After traversing it, we come back to the node 7. After visiting the left subtree of 7, we print 7 and go to the right subtree of 7 which is NULL.

After the call inorder (NULL) we have traversed the tree having 7 as the root and it is a left subtree of 9. Thus we have visited the left subtree of 9. We print the number 9 before going to traverse its right subtree. The right subtree of 9 is NULL so the recursion ends here and we come back to the node 4. The tree having node 4 as root has been traversed now. This tree is a left subtree of node 14. Thus after traversing it we come back to node 14 and print it (as we have traversed its left subtree i.e. tree with 4 as root). It is evident here that before going to traverse the right subtree of 14, we have printed the numbers 3, 4, 5, 7, 9 and 14.

Now after printing the number 14, we go to traverse the right subtree of 14. The traversal of this right subtree with 15 as a root, is being carried out in the way, we traversed the left subtree. In the right subtree, we reach at node 15 and look at its left subtree before printing it. This left subtree is NULL. The call inorder (NULL) makes the condition of if statement false and we come back to the root node i.e. 15. We print this number and go to the right subtree of 15. The right subtree of 15 is also a tree the root node of which is 18. From this root node i.e. 18, we go to its left subtree and reach at node 16. NULL being the left subtree of 16, makes us to return to 16 and print it (as its left subtree has been traversed, which is NULL). After printing 16, we go to the right subtree of 16. This leads us to node 17. As we are traversing the tree by inorder process, so before printing the value 17, it will be necessary to go to traverse its left subtree. Its left subtree is NULL. So after the call inorder (NULL) we return to 17 and print it. Now we look at the right subtree of 17 that is also NULL. So again there is a call inorder (NULL) which ends the recursive calls for this tree. Thus we have traversed the whole tree having node 17 as root and it is a right subtree of 16. We have already traversed the left subtree of 16.

So we have traversed the tree with node 16 as its root. This tree is a left subtree of node 18. After traversing the left subtree of 18, we print the number 18 and go to its right subtree and reach at node 20. Now we go to the left subtree of 20 i.e. NULL and come back to 20 and print it. Then go to its right subtree, which is also NULL that ends the recursion. Thus we have traversed the tree having node 20 as its root. This tree (having 20 as root) is a right subtree of 18 which itself is a right subtree of 15. We have already traversed the left subtree of 15 and gone through the whole tree having 15 as root. This tree is a right subtree of the main tree with 14 as the root. We have already traversed its left subtree. So we have traversed the whole tree by the inorder process. From the figure 14.3 we see that by the inorder traversal we have printed the numbers in the order as below

3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20

We have successfully demonstrated the preorder and inorder traversal of a tree by using recursion method. The postorder traversal has been left for you as an exercise. You can do it with the same above tree or build a tree on your own and traverse it.

The tree data structure by nature is a recursive data structure. In the coming lecture, we will see that most of the methods we write for tree operations are recursive. From the programming point of view, the recursion is implemented internally by using call stack. This stack is maintained by the run time environment. The recursion is there in the machine code generated by the compiler. It is the programmer’s responsibility to provide a terminating condition to stop the recursion. Otherwise, it will become an infinite recursion. If we do not put a terminating condition, the recursive calls will be continued and the call stack will go on increasing. We know that when a program executes, it becomes a process and some memory is allocated to it by the system for its call stack. This memory has a limit. Thus when the recursive calls do not end, there is no memory left to be used for increasing call stack after a certain time. This will crash the program or the program will halt. So we should be very careful while using the recursive calls and ensure the provision of a terminating condition in the recursive calls.

Non Recursive Traversal

We can also carry out these traversing with the help of non-recursive calls. Think for a few moments that how can we keep track of going left or going right or coming back to the node with out using the recursion.. In the preorder, inorder and postorder traversal, we visit nodes at different level and then return. We know the way to comeback or go further deep. Now if we are not using the recursion, how these things can be managed? We have to manage all this in our methods. Let’s see how we can write the non-recursive tree traversal methods. We can implement non-recursive versions of the preorder, inorder and postorder traversal by using an explicit stack. We cannot avoid stack. The stack will be used to store the tree nodes in the appropriate order. Let’s try to write methods without using recursion. For this purpose, we have to create stack.

Here, for example, is the routine for inorder traversal that uses a stack.

void inorder(TreeNode<int>* root)
{
Stack<TreeNode<int>* > stack;
TreeNode<int>* p;
p = root;
do
{
while( p != NULL )
{
stack.push( p );
p = p->getLeft();
}
// at this point, left tree is empty
if( !stack.empty() )
{
p = stack.pop();
cout < *(p->getInfo()) < " ";
// go back & traverse right subtree
p = p->getRight();
}
} while ( !stack.empty() || p != NULL );
}

The signature is same. The name of the function that is inorder, its return type is void and the argument is pointer to TreeNode. Then there is stack abstract data type. We can store int, float or other data type in the stack. Here we want to store the TreeNode in the stackand then in the nodes we want to store integers. The statement is: