#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Tree traversal functions
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d -> ", root->item);
  inorderTraversal(root->right);
}

void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d -> ", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d -> ", root->item);
}

// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// Insert a node on the left of the parent node
struct node* insertLeft(struct node* parent, int value) {
  parent->left = createNode(value);
  return parent->left;
}

// Insert a node on the right of the parent node
struct node* insertRight(struct node* parent, int value) {
  parent->right = createNode(value);
  return parent->right;
}

int main() {
  //!showMemory() 
  struct node* root = createNode(1);
  struct node* leftNode = insertLeft(root, 12);
  struct node* rightNode = insertRight(root, 9);

  insertLeft(leftNode, 5);
  insertRight(leftNode, 6);

  printf("Inorder traversal:\n");
  inorderTraversal(root);

  printf("\n\nPreorder traversal:\n");
  preorderTraversal(root);

  printf("\n\nPostorder traversal:\n");
  postorderTraversal(root);

  return 0;
}