I made a program that takes user input to create a binary tree, with options to traverse said tree based on user input. Inserting and Preorder traversal work fine, but for some reason Inorder traversal prints the same output as Preorder, and Postorder traversal prints the input backwards. I've checked my insert and traversal functions a million times and I can't see where I'm going wrong... help would be greatly appreciated!

#include <iostream> 
using namespace std; 
  
struct Node {   
    int data;
    Node *right;
    Node *left;
};


Node *createNode(int data) {
    Node *temp = new Node();
    temp->data = data;
    temp->right = temp->left = NULL;
    return temp;
}


void insertNode(Node* &root, int data) {  
    if(root == NULL)
        root = createNode(data);
    else if(root->data > data)  
        insertNode(root->left, data); 
    else
        insertNode(root->right, data);
}


void printInorder(Node *root) { 
    if(root != NULL){
        printInorder(root->left); 
        cout << root->data << " "; 
        printInorder(root->right); 
    }
}


void printPreorder(Node *root) {
    if(root != NULL){
        cout << root->data << " "; 
        printPreorder(root->left); 
        printPreorder(root->right); 
    }
}


void printPostorder(Node *root) { 
    if(root != NULL){
        printPostorder(root->left);
        printPostorder(root->right);
        cout << root->data << " ";
    }
}

  
int main() 
{ 
    Node *root = NULL;  
    int n, val;         
    int treeOp;
    
    do {                
        
        cout << "\nBINARY TREE OPTIONS";
        cout << "\n------------------------------\n";
        cout << "(1) Insert element(s)";
        cout << "\n(2) Inorder traversal";
        cout << "\n(3) Preorder traversal";
        cout << "\n(4) Postorder traversal";
        cout << "\n(5) Return to main menu\n\n";
        cout << "Enter the number of your choice: ";
        cin >> treeOp;
        cout << endl;
        
        switch(treeOp) {
            case 1: 
                cout << "How many elements will you insert: "; 
                cin >> n;
                cout << "\nInsert " << n <<" elements, hit enter after each:\n";
                for(int i=0; i < n; i  ) {
                    cin >> val, insertNode(root, val); 
                }
                cout << "\nElement(s) inserted!" << endl;
                break;
            case 2:
                if(root == NULL) {
                    cout << "\nNo elements found!\n";
                } else {
                    cout << "INORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printInorder(root); 
                    cout << endl;
                }
                break;
            case 3:
                if(root == NULL) {
                    cout << "\nNo elements found!\n";
                } else {
                    cout << "PREORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printPreorder(root);
                    cout << endl;
                }
                break;
            case 4:
                if(root == NULL) {
                    cout << "\nNo elements found!\n"; 
                } else {
                    cout << "POSTORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printPostorder(root);
                    cout << endl;
                }
                break;
            default:
                if(treeOp!=5){
                    cout << "\nInput invalid, please try again\n";
                }
        }
        
    } while (treeOp != 5);      
  
    return 0; 
} 

Not sure if I was clear in my explanation above, but basically when I insert 1 2 3 4 5, I'd get:

• Inorder: 1 2 3 4 5 (wrong)
• Preorder: 1 2 3 4 5 (right)
• Postorder: 5 4 3 2 1 (wrong)

CodePudding user response：

You did not make a mistake at all. But you have now first-hand encountered the raison d'être for tree balancing. (eg red-black trees or AVL trees)

Inserting "1 2 3 4 5" in that order, with your code, gives the following tree (also known as a linked list):

1
  2
    3
      4
        5

If you change your input to "3 1 2 4 5" you get a far more balanced tree:

     3
   1   4
    2   5

CodePudding user response：

The inputs (1,2,3,4,5) is sorted, and on inserting them gives rise to a skewed tree structure.

    >       1
    >     /   \
    > left(1)  2
    >          / \
    >    left(2)  3
    >             / \
    >       left(3)  4
    >                / \
    >          left(4)  5
    >                   / \
    >            left(5)  right(5)

In case of pre-order traversal, all left nodes are NULL and so it will print root first and move to right. So, in preorder traversal it shall print

left(1)---->1--->left(2)--->2--->left(3)--->3--->(left 4)---->4---->(left 5)--->5---->right(5)

Since, with the given inputs left(1), left(2),left(3),left(4),left(5) and right(5) are null, the sequence printed as 1,2,3,4,5 is correct for pre-order traversal.

Similarly, you can do analyses for other traversals.