preorder traversal using recursion

[riya1234]

i have made this program for creating and traversing binary search tree. for inorder, it is working well but for post and pre order it showing wrong results .i could not be able to get the problem .could some one please tell me problem regarding this program .it is written in c++

#include<iostream.h>
#include<conio.h>
#include<process.h>
 struct tree_node
 {
 tree_node *left;
 tree_node *right;
 int data;
 } ;
 class bst
 {
 tree_node *root;
 public:
 bst()
 {
 root=NULL;
 }
 int isempty() {
 return(root==NULL);
 }

 void insert(int item);
 void inordertrav();
 void inorder(tree_node *);
 void postordertrav();
 void postorder(tree_node *);
 void preordertrav();
 void preorder(tree_node *);
};
 void bst::insert(int item)
 {
 tree_node *p=new tree_node;
 tree_node *parent;
 p->data=item;
 p->left=NULL;
 p->right=NULL;
 parent=NULL;
 if(isempty())
 root=p;
 else
 {
 tree_node *ptr;
 ptr=root;
 while(ptr!=NULL)
 {
 parent=ptr;
 if(item>ptr->data)
 ptr=ptr->right;
 else
 ptr=ptr->left;
 }
 if(item<parent->data)
 parent->left=p;
 else
 parent->right=p;
 }}

 void bst::inordertrav()
 {
 inorder(root);
 }
 void bst::inorder(tree_node *ptr)
 {
 if(ptr!=NULL)
 {
 inorder(ptr->left);
 cout<<"  "<<ptr->data<<"     ";
 inorder(ptr->right);
 }
 }
 void bst::postordertrav()
 {
 postorder(root);
 }
 void bst::postorder(tree_node *ptr)
 {
 if(ptr!=NULL)
 {
 postorder(ptr->left);
 postorder(ptr->right);
 cout<<"  "<<ptr->data<<"     ";
 }
 }

 void bst::preordertrav()
 {
 preorder(root);
 }
 void bst::preorder(tree_node *ptr)
 {
 if(ptr!=NULL)
 {
 cout<<"  "<<ptr->data<<"     ";
 preorder(ptr->left);
 preorder(ptr->right);
 }
  }

 void main()
       {
       bst b;

       b.insert(52);
	   b.insert(25);
	    b.insert(50);
	     b.insert(15);
	       b.insert(40);
		b.insert(45);
		b.insert(20); cout<<"inorder"<<endl;
                b.inordertrav();

	        cout<<endl<<"postorder"<<endl;
		b.postordertrav();
		cout<<endl<<"preorder"<<endl;
		b.preordertrav();
	   
	       getch();
	       }

[Lerner]

>>for post and pre order it showing wrong results

Other than questonable indentation practices and some overuse of pointers in the insertion process I don't see any obvious logic errors visually. So. let's see if what you're expecting is what others would expect, too. Post a sample input using 4-6 values, what you would expect for preorder and postorder traversal, and what your program is giving you for preorder and postorder traversal.

BTW congratulations on using code tags on your first post! However, if the indentation you use in your code looks like it does in the post, you should really work on it. Many respected people who post here won't look at poorly formattted code, meaning you'll be missing a significant opportunity for additional assistance.

Oh, and one last thing, it's int main() , not void main(). Even if your current compiler let's you get away with the void main() schtick, you shouldn't do it.

[riya1234]

thanks for your reply and sorry for the mistake i have made in my first post about indentation. as i am in the first year of my degree ,i really didnot think that it holds that much importance but thanks for giving me this valuable suggestion that sometime people ignore the posts with bad indentation.

you have asked for the actual and the expected results. this are as follows
52,25,50,15,40,45,20(values needed to be entered one by one)
actual (wrong results)
inorder
15 20 25 40 45 50 52(this is write output)
postorder
20 15 45 40 50 25 52
preorder
52 25 15 20 50 40 45

expected results
inorder
15 20 25 40 45 50 52
postorder
15 25 20 45 52 50 40
preorder
40 20 15 25 50 45 52

hope to get your response soon.

[Lerner]

Your insert function looks like it is:
1) put the first value entered into root.
2) then start at root and if next value is less than current value go left, else go right, until you find a null pointer and insert there.
If you agree with that interpretation, then can we agree the tree would look something like this if it were written down?

50
                            /
                          25
                        /    \
                      /        \
                   15          50
                     \          /
                      20      40
                                 \
                                   45

[Lerner]

Assuming you agree with the tree as posted, then I offer the following.

1) I describe preorder traversal as print every new node as you come to it. Start at root. Then after each print look left first and if nothing on left look right. Don't print node already printed. Using that pattern and printing out singleton blanks, if there are any, then I would get:

52, 25, 15, blank 15L, 20, 50, 40, blank 40L, 45, blank 50R, blank52R

and if you leave out the blanks then I get
52, 25, 15, 20, 50, 40, 45

which is the actual result your program gave. Therefore I would ask you to post how you would explain how to do a preorder traversal to get the results you expect.

2) I explain postorder traversal as go as starting at root look left. If you can go left, go. If you can't look right and repeat. When you can't go any further then print and go back as needed printing each node only after you've looked both left and right for each node and can't go there (or can't go there again). Using that description I get:

20, 15, 45, 40 50, 25, 52

which is what your program printed. Please print your explanation of how postorder traversal works.

3) I describe inorder traversal to be start at root and go left as far as you can. Then print. Then go right as far as you can. Then repeat. Using this description I get:

15, 20, 25, 40, 45, 50, 52

which is what your program prints and what you expect. Hopefully this is how you describe inorder traversal as well.