Problem regarding a c++ program.

This is a tricky question that most students get puzzled.  this is nothing but the in order  traversal of a binary search tree. In recursive order , you may write,

inorder ( BST *tree ){

if( tree == NULL)

 return;

inorder ( tree -> left );

cout << tree -> data;

inorder ( tree -> right );

}

You can also use a non recursive version by using a stack and the code is lengthy comparatively. The root is alwars printed after the left sub-tree and before the right sub tree. In fact, all the node data are printed after traversing the left sub tree and before the right sub tree.

 

However the pre or Post order traversals will not do the job. 

A Binary search tree has all its small values than the root at the left sub tree and the larger valuues to its right. Thus We know, that the values are printed in ascending order for a Binary Search Tree. Hence the Root will be at the middle of the left and right sub trees.

Thanks.