CS21003 Algorithms I
 CS29003 Algorithms Laboratory
Autumn 2012, L-T-P: 3-1-0 
L-T-P: 0-0-3 

Programming Assignment 6

The inorder traversal of a binary search tree (BST) prints the key values in sorted order. In the class, we have seen a recursive function for carrying out the in-order traversal. In this exercise, you implement the in-order traversal of a BST using only a constant amount of extra space. This implies the following.

The idea behind this traversal algorithm is explained in the following figure. The pointer p points to the node which we are currently visiting. The parent of p is pointed to by another pointer q. If p points to the root, then q is NULL. The links from the root to the node pointed to by q are appropriately reversed so that these pointers function as parent pointers.

At any node, four types of movements are possible:

Write a program to do the following.

Sample output

   Initializing the tree
   T = ()
   Inserting 35
   T = (35)
   Inserting 33
   T = (33,35)
   Inserting 58
   T = (33,35,58)
   Inserting 10
   T = (10,33,35,58)
   Inserting 99
   T = (10,33,35,58,99)
   Inserting 73
   T = (10,33,35,58,73,99)
   Inserting 61
   T = (10,33,35,58,61,73,99)
   Inserting 42
   T = (10,33,35,42,58,61,73,99)
   Inserting 6
   T = (6,10,33,35,42,58,61,73,99)
   Inserting 36
   T = (6,10,33,35,36,42,58,61,73,99)
   Inserting 6
   T = (6,10,33,35,36,42,58,61,73,99)
   Inserting 60
   T = (6,10,33,35,36,42,58,60,61,73,99)
   Freeing the tree
   T = ()

Submission Site

Back | Home