/* 
* Code example for CP264 Data Structures II
* General tree
* tree traversal, pre-order, in-order, post-order, breadth-first-order
* tree search, depth-first-search, breadth-first-search
* HBF 
*/

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

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

tnode *new_node(int);
void print_preorder(tnode*);
void print_inorder(tnode*);
void print_postorder(tnode*);
void print_breadth_first_order(tnode*);  //print in breadth-first-order
tnode *bfs(tnode*, int);
tnode *dfs(tnode*, int);
void print_tree(tnode*, int);
void clean_tree(tnode**);

typedef struct queue_node {
  tnode *tnp;
  struct queue_node *next;
} qnode;

void enqueue(qnode **, qnode**, tnode*);
void dequeue(qnode **, qnode **);
void clean_queue(qnode **, qnode **);

int main() {
  tnode *np, *root = NULL;
  tnode *n1 = new_node(1);
  tnode *n2 = new_node(2);
  tnode *n3 = new_node(3);
  tnode *n4 = new_node(4);
  tnode *n5 = new_node(5);
  tnode *n6 = new_node(6);
  tnode *n7 = new_node(7);  
  n1->left = n2;
  n1->right = n3;
  n2->left = n4;
  n2->right = n5;
  n3->left = n6;
  n3->right = n7;
  
  root = n1;
  printf("tree style\n");
  print_tree(root, 0);
  
  printf("\npre-order: ");
  print_preorder(root);  
  
  printf("\nin-order: ");
  print_inorder(root);
  
  printf("\npost-order: ");
  print_postorder(root);
  
  printf("\nbreadth-first-order: ");
  print_breadth_first_order(root);
  
  np = bfs(root, 7);
  if (np)
    printf("\nBreadth-first-search found: %d", np->data);
  else
    printf("\nBreadth-first-search not found");

  np = bfs(root, 10);
  if (np)
    printf("\nBreadth-first-search found: %d ", np->data);
  else
    printf("\nBreadth-first-search not found");


  np = dfs(root, 7);
  if (np)
    printf("\nDepth-first-search found: %d", np->data);
  else
    printf("\nDepth-first-search not found");

  np = dfs(root, 10);
  if (np)
    printf("\nBDepth-first-search found: %d ", np->data);
  else
    printf("\nDepth-first-search not found");

  clean_tree(&root);

  return 0;
}

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

// recursive algorithm
void print_preorder(tnode *root) {
  if (root) {
    printf("%d ", root->data);
    print_preorder(root->left);
    print_preorder(root->right);
  }
}

// recursive algorithm
void print_inorder(tnode *root) {
  if (root) {
    print_inorder(root->left);
    printf("%d ", root->data);
    print_inorder(root->right);
  }
}

// recursive algorithm
void print_postorder(tnode *root) {
  if (root) {
    print_postorder(root->left);
    print_postorder(root->right);
    printf("%d ", root->data);
  }
}

// recursive algorithm
void print_tree(tnode *root, int prelen) {
  int i;
  if (root != NULL) {
    for (i = 0; i < prelen; i++)
      printf("%c", ' ');
    printf("%s", "|___");
    printf("%d\n", root->data);
    print_tree(root->right, prelen + 4);	
    print_tree(root->left, prelen + 4);
  }
}

// recursive algorithm
void clean_tree(tnode **rootp) {
  tnode *root = *rootp;
  if (root) {
    if (root->left)
      clean_tree(&root->left);
    if (root->right)
      clean_tree(&root->right);
    free(root);
  }
  *rootp = NULL;
}

// recursive algorithm
tnode *dfs(tnode *root, int val) {
  if (!root) {
    return NULL;
  }
  tnode *np;

  if (val == root->data) return root;
  
  np = dfs(root->left, val);
  if (np) 
    return np;
  else 
    return dfs(root->right, val);  

  return NULL;
}

void enqueue(qnode **frontp, qnode **rearp, tnode *treenode) {
   qnode *qnp = (qnode*) malloc(sizeof(qnode));
   if (qnp == NULL) return;
   else {
   qnp->tnp = treenode;
     qnp->next = NULL;
   
     if (*frontp == NULL) 
    *frontp = qnp;
   else 
       (*rearp)->next = qnp;
   
   *rearp = qnp;
   }
}

void dequeue(qnode **frontp, qnode **rearp) {
   if (*frontp == NULL) return;
   else {
      qnode *qnp = *frontp;
    if (*frontp == *rearp) {
     free(qnp); 
     *frontp = NULL;
     *rearp = NULL;
    } else {
    *frontp = qnp->next;
    free(qnp); 
    }
   }   
}

void clean_queue(qnode **frontp, qnode **rearp) {
  qnode* qnp = *frontp, *temp;
  while (qnp != NULL) { 
  temp = qnp; 
  qnp = qnp -> next;
  free(temp);
  }
  *frontp = NULL;
  *rearp = NULL;
}

// iterative algorithm
void print_breadth_first_order(tnode *root) {
  if (root == NULL) return;
  tnode *np;
  qnode *front = NULL, *rear = NULL; 
  enqueue(&front, &rear, root);
  while (front) {
    if (front->tnp) {
       np = front->tnp;
	   printf("%d ", np->data); 
       enqueue(&front, &rear, np->left);
       enqueue(&front, &rear,  np->right);
    } 
    dequeue(&front,&rear);
  }
}

// iterative algorithm
tnode *bfs(tnode *root, int val) {
  if (!root) {
    return;
  }
  tnode *np;
  qnode *front = NULL, *rear = NULL;  

  enqueue(&front, &rear, root);

  while (front) {
    if (front->tnp) {
       np = front->tnp; 
       if (np->data == val) {
        clean_queue(&front, &rear);
        return np;
       } 
       else {
         enqueue(&front, &rear, np->left);
         enqueue(&front, &rear,  np->right);
       }
    } 
    dequeue(&front,&rear);
  }
  return NULL;
}

/*
tree style
|___1
    |___3
        |___7
        |___6
    |___2
        |___5
        |___4

pre-order: 1 2 4 5 3 6 7
in-order: 4 2 5 1 6 3 7
post-order: 4 5 2 6 7 3 1
breadth-first-order: 1 2 3 4 5 6 7
Breadth-first-search found: 7
Breadth-first-search not found
Depth-first-search found: 7
Depth-first-search not found
*/