inorder and preorder traversal using recursion - binary search tree c++

Question

so i need to implement a member function, pre-order and inorder traversal of a binary search tree using recursion. i'm having trouble implementing all three, since they're coming out with the wrong outputs. The traversals are supposed to add data values it encounters to a given linked list.

My member function only prints out the right nodes of the tree. I have attached my code, and it would be amazing if someone could give me some pointers as to where the errors lie and why the output is not printing what it's supposed to be. Thanks in advance!!!

Output I currently get:

size of test BinaryTree: 11  
member true for 8  
member true for 38  
member true for 39  
member true for 45  
pre order: [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 45, 45]  
in order: [8, 8, 8, 8, 38, 38, 38]

Output I want:

size of test BinaryTree: 11  
member true for 1  
member true for 3  
member true for 4  
member true for 7  
member true for 8  
member true for 16  
member true for 31  
member true for 33  
member true for 38  
member true for 39  
member true for 45  
pre order: [8, 4, 3, 1, 7, 38, 31, 16, 33, 39, 45]  
in order: [1, 3, 4, 7, 8, 16, 31, 33, 38, 39, 45]

My code:

bool BinaryTreeNode::member(Data * newData) {
   if (newData->compareTo(this->nodeData) == 0) {
           return true;
    }
   else if (newData->compareTo(this->nodeData) == -1) {
         if (left == NULL)
             return false;
        else
             return left->member(newData);
}
   else if (newData->compareTo(this->nodeData) == 1) {
        if (right == NULL)
           return false;
        else
           return right->member(newData);
}
return false;
    }        

    void BinaryTreeNode::preorderTraversal(LinkedList * result) const {
    result->insert(nodeData);
        if (left != NULL) left->preorderTraversal(result);
    result->insert(nodeData);
    if (right != NULL) right->preorderTraversal(result);
        }

    void BinaryTreeNode::inorderTraversal(LinkedList * result) const {
    if (left != NULL) {
         left->inorderTraversal(result);
         result->insert(nodeData);
    }
    if (right != NULL) {
         right->inorderTraversal(result);
    }
    }

Answer 1

#include<conio.h>
#include<iostream>
using namespace std;
  struct node
  {
         int data;
         node *left,*right;       
  };
         void add(node **root)
         {
              node *temp,*save,*r;
              temp=*root;
              int num;
              cout<<"Enter node in BST\t";
              cin>>num;
              if(*root==NULL)
              {
                            cout<<"Root:"<<num<<"\n";
                            temp=new node;
                            temp->data=num;
                            temp->left=NULL;
                            temp->right=NULL;
                            *root=temp;              
              }
              else
              {
                            temp=*root;
                            while(temp!=NULL)
                            {
                                   if(temp->data>num)
                                   {
                                          save=temp;
                                          temp=temp->left;                 
                                   }                 
                                   else
                                   {
                                          save=temp;
                                          temp=temp->right;    
                                   }
                            }    
                            if(save->data>num)
                            {
                                   r=new node;
                                   r->data=num;
                                   r->left=NULL;
                                   r->right=NULL;
                                   save->left=r;
                                   temp=r;                  
                            }
                            else
                            {
                                   r=new node;
                                   r->data=num;
                                   r->left=NULL;
                                   r->right=NULL;
                                   save->right=r;
                                   temp=r;    
                            }
              }
         }
         void pre(node **root)
         {
              node *temp,*save;
              node *stack[100],*r;
              int top;
              temp=*root;
              if(*root==NULL)
              {
                           cout<<"=> No node in BST\n\n";
                           return;             
              }
              else
              {
                  while(temp!=NULL)
                  {
                       cout<<temp->data<<"\n";
                       if(temp->right!=NULL)
                       {
                              stack[++top]=temp->right;           
                       }    
                     if(temp->left!=NULL)
                     {
                             temp=temp->left;        
                     }
                     else
                     {
                             temp=stack[top];
                             top--;
                             delete stack;    
                     }
                  }
              }
         }
         //Below all is using recursion
int preorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 cout<<root->data<<"\n";
 preorder(root->left);
 preorder(root->right);
}
int inorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 inorder(root->left);
 cout<<root->data<<"\n";
 inorder(root->right);
}
int postorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 postorder(root->left);
 postorder(root->right);
  cout<<root->data<<"\n";
}
int main()
{
int n;
node *p=NULL;
cout<<"Binary search tree\n";
while(n!=6)
{
        cout<<"Select: 1.Insert node in BST\n\t2.Pre-order traversal\n\t3.Pre-order    \n\t4.Inorder\n\t5.Postorder\n\t6.Exit\t";
        cin>>n;
        switch(n)
        {
                 case 1:add(&p);break;
                 case 2:pre(&p);break;
                 case 3:preorder(p);break;
                 case 4:inorder(p);break;
                 case 5:postorder(p);break;
                 case 6:cout<<"Program ends\n";break;
                 default:printf("=> Wrong option selected,Try again\n \n");break;         
        }        
}
getch();
return 0;     
}

Answer 2

Well, your inorder only inserts the actual node data into the result if there has been a left subtree. The data insert should be unconditional:

if (left != NULL) left->inorderTraversal(result);
result->insert(nodeData);
if (right != NULL) right->inorderTraversal(result);

Your preorder inserts the data twice, but looks ok otherwise.

Answer 3

Preorder:

do stuff with the node // pre means before
recurse left
recurse right

Inorder:

recurse left
do stuff with the node // in means inside
recurse right

Postorder:

recurse left
recurse right
do stuff with the node // post means after