Why my code won't do preorder form correctly in Binary Search Tree?

Question

I edited a code for a binary search tree, for strings. But there's a small problem. When I enter a simple input like A B C D E F, my program says the pre-order form is A B C D E F... which it should actually be A B D E C F.

Since, it should print the word at the root then print the word at the left subtree in pre-order and then print the word at the right subtree in pre-order.

Post order also should print D E B F C A but it prints A B C D E F and in-order should've printed D B E A F C... but it just gave me F E D C B A.

Any help is appreciated, I don't know what went wrong.

Here is the working full source code:

#include <iostream>
#include <string>
#include <conio.h>
using namespace std;

class Node {
string word;
Node* left;
Node* right;
public:
Node() { word=-1; left=NULL; right=NULL; };
void setWord(string aWord) { word = aWord; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
string Word() { return word; };
Node* Left() { return left; };
Node* Right() { return right; };
};

class Tree {
 Node* root;
public:
 Tree();
 ~Tree();
 Node* Root() { return root; };
 void addNode(string word);
 void inOrder(Node* n);
 void preOrder(Node* n);
 void postOrder(Node* n);
private:
 void addNode(string word, Node* leaf);
 void freeNode(Node* leaf);
};

Tree::Tree() {
 root = NULL;
}

Tree::~Tree() {
 freeNode(root);
}

void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
   freeNode(leaf->Left());
   freeNode(leaf->Right());
   delete leaf;
}
}

void Tree::addNode(string word) {
 if ( root == NULL ) {
    Node* n = new Node();
    n->setWord(word);
    root = n;
 }
 else {
   addNode(word, root);
 }
 }

void Tree::addNode(string word, Node* leaf) {
if ( word <= leaf->Word() ) {
   if ( leaf->Left() != NULL )
      addNode(word, leaf->Left());
   else {
      Node* n = new Node();
      n->setWord(word);
      leaf->setLeft(n);
   }
}
else {
   if ( leaf->Right() != NULL )
      addNode(word, leaf->Right());
   else {
      Node* n = new Node();
      n->setWord(word);
      leaf->setRight(n);
   }
}
}

void Tree::inOrder(Node* n) {
if ( n ) {
   inOrder(n->Left());
   cout << n->Word() << " ";
   inOrder(n->Right());
}
}

void Tree::preOrder(Node* n) {
if ( n ) {
   cout << n->Word() << " ";
   preOrder(n->Left());
   preOrder(n->Right());
}
}


void Tree::postOrder(Node* n) {
if ( n ) {
   postOrder(n->Left());
   postOrder(n->Right());
   cout << n->Word() << " ";
}
}

int main() {
string word;
Tree* tree = new Tree();
while(word != "end"){
   cin >> word;
   if(word == "end"){
       break;
   }
   tree->addNode(word);
}

cout << "In order traversal" << endl;
tree->inOrder(tree->Root());
cout << endl;

cout << "Pre order traversal" << endl;
tree->preOrder(tree->Root());
cout << endl;

cout << "Post order traversal" << endl;
tree->postOrder(tree->Root());
cout << endl;

delete tree;
_getch();
return 0;
}

Answer 1

In your test example A B C D E F your tree is basically a linked list. First, you insert A, so it becomes your new root. B is bigger than A, so when you insert it, it goes as a right child. The same happens for all next strings:

A->B->C->D->E->F.

So when you traverse your tree from left, you just print your list as it is since there are no left child in any of the nodes in the tree. When you traverse it from the right, you just print it backwards.

Since your tree is unbalanced, this is an expected behaviour. There are no bugs in your code from what I can see. Try to add balancing or make another root.