I have written code to insert and print Binary Search Tree, but while pre-order traversal i am not getting correct output. Below is the logic used :
#include<iostream>
using namespace std;
class BSTree
{
class Node
{
public:
int key;
int count;
Node *lChild,*rChild;
};
public:
Node *root;
BSTree()
{
root = new Node();
root=NULL;
}
Node* createNewNode(int key)
{
Node *newNode = new Node();
newNode->key = key;
newNode->count = 0;
newNode->lChild = NULL;
newNode->rChild = NULL;
return newNode;
}
Node* appendNode(Node* node,int key)
{
if(node==NULL)
{
if(root == NULL)
{
root = createNewNode(key);
return root;
}
else
return createNewNode(key);
}
if(key < node->key)
node->lChild = appendNode(node->lChild,key);
else if(key > node->key)
node->rChild = appendNode(node->rChild,key);
return node;
}
void printBSTree(Node *node)
{
if(node == NULL)
return;
printBSTree(node->lChild);
cout<<node->key<<" ";
printBSTree(node->rChild);
}
void printPreBSTree(Node *node)
{
if(node != NULL)
{
cout<<node->key<<" ";
printBSTree(node->lChild);
printBSTree(node->rChild);
}
}
Node* findInOrderSucc(int key)
{
}
Node* findNode(Node *node,int key)
{
cout<<"key = "<<node->key<<" "<<key<<endl;
if(node==NULL)
return node;
if(node->key == key)
return node;
findNode(node->lChild,key);
findNode(node->rChild,key);
}
deleteKey(int key)
{
Node* deletedNode = findNode(root,key);
cout<<endl<<deletedNode->key<<endl;
}
};
int main()
{
BSTree obj;
obj.appendNode(obj.root,50);
obj.appendNode(obj.root,30);
obj.appendNode(obj.root,20);
obj.appendNode(obj.root,40);
obj.appendNode(obj.root,70);
obj.appendNode(obj.root,60);
obj.appendNode(obj.root,80);
obj.printBSTree(obj.root);
cout<<endl;
obj.printPreBSTree(obj.root);
return 0;
}
Output which this code is giving is :
20 30 40 50 60 70 80
50 20 30 40 60 70 80
while correct output is :
20 30 40 50 60 70 80
50 30 20 40 70 60 80
Please suggest what I am doing wrong while inserting.