/*
 * modified from textbook example
 * HBF
*/
#include <stdio.h>
#include <malloc.h>

typedef struct tree_node {
  int data;
  int thread;  
  struct tree_node *left, *right;
} tnode;

tnode *new_node(int val);
void insert_node(tnode **rootp, tnode *new_np, tnode *rt);
void print_inorder(tnode *root);

int main() {
  tnode *root = NULL;
  insert_node(&root, new_node(5), NULL);
  insert_node(&root, new_node(7), NULL);  
  insert_node(&root, new_node(2), NULL);
  insert_node(&root, new_node(4), NULL);  
  insert_node(&root, new_node(3), NULL);
  insert_node(&root, new_node(2), NULL);
  insert_node(&root, new_node(6), NULL);  
  insert_node(&root, new_node(9), NULL);  
  insert_node(&root, new_node(1), NULL);  
  insert_node(&root, new_node(8), NULL);
  print_inorder(root);
  return 0;
}

tnode *new_node(int val) {
  tnode *tnp = (tnode*) malloc(sizeof(tnode));
  if (tnp == NULL) {
    return NULL;
  }
  else {
    tnp->data = val;
    tnp->left = tnp->right = NULL;
    tnp->thread = 0;
    return tnp;
  }
}

void insert_node(tnode **rootp, tnode *new_np, tnode *rt) {
  if (rootp == NULL || new_np == NULL) return;
  
    tnode *root = *rootp;
  if (root == NULL) {
    root = new_np;
    if (rt) {
      root->right = rt;
      root->thread = 1;
    }
    *rootp = root;
  }
  else if (new_np->data == root->data) {
    return;
  }
  else if (new_np->data < root->data) {
    insert_node(&root->left, new_np, root);
  }
  else if (root->thread == 1) {
    root->right = new_np;
    if (rt) {
      new_np->right = rt;    
      new_np->thread = 1;
    }
    root->thread = 0;
  }
  else {
    insert_node(&root->right, new_np, rt);
  }  
}


void print_inorder(tnode *root) {
  tnode *tnp = root, *prev;
  do {
    while (tnp != NULL) {
      prev = tnp;
      tnp = tnp->left;
    }
    if (prev != NULL) {
      printf(" %d", prev->data);
      tnp = prev->right;
      while (prev != NULL && prev->thread) {
        printf(" %d", tnp->data);
        prev = tnp;
        tnp = tnp->right;
      }
    }
  } while (tnp != NULL);
}

/*
1 2 3 4 5 6 7 8 9
*/