Implement inorder, preorder and postorder traversal methods in binary search tree in C++

Code

// Binary Search Tree operations in C++

#include <iostream>
using namespace std;

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    cout << root->key << " -> ";

    // Traverse right
    inorder(root->right);
  }
}

// preorder Traversal
void preorder(struct node *root) {
  if (root != NULL) {
    // Traverse root
    cout << root->key << " -> ";

    // Traverse left
    preorder(root->left);

    // Traverse right
    preorder(root->right);
  }
}

// postorder Traversal
void postorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    postorder(root->left);

    // Traverse right
    postorder(root->right);

    // Traverse root
    cout << root->key << " -> ";
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}



// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  cout << "Inorder traversal: "<< endl;
  inorder(root);

  cout << endl << "Preorder traversal: "<< endl;
  preorder(root);

  cout << endl << "Postorder traversal: "<< endl;
  postorder(root);

  cout << endl;

  return 0;
}


Output

Inorder traversal: 
1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 14 -> 
Preorder traversal: 
8 -> 3 -> 1 -> 6 -> 4 -> 7 -> 10 -> 14 -> 
Postorder traversal: 
1 -> 4 -> 7 -> 6 -> 3 -> 14 -> 10 -> 8 ->