inorder and preorder traversal using recursion - binary search tree c++
Solution 1
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
Solution 2
#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;
}
Solution 3
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.
user1333781
Updated on July 10, 2020Comments
-
user1333781 almost 4 years
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); } }