#include "trees.h"


node_t* createNode(int val){
  node_t *newNode = malloc(sizeof(node_t));
  newNode->val = val;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
tree_t* createTree(){
  tree_t *newTree = malloc(sizeof(tree_t));

  newTree->root = createNode(0);
  return newTree;
}

int addNode(node_t *node, int val, const char lr){
  if(lr == 'l'){
    node->left = createNode(val);
  }else if(lr == 'r'){
    node->right = createNode(val);
  }else{
    return -1;
  }
  return 0;
}

int changeNode(node_t *node, int val){
  if(node){
    node->val = val;
    return 0;
  }
  return -1;
}

void printNode(node_t node){
  printf("( %d ", node.val);
  if(node.left != NULL){
    printf("L");
    printNode(*node.left);
  }
  if(node.right != NULL){
    printf("R");
    printNode(*node.right);
  }
  printf(") ");
}

void printTree(tree_t tree){
  printNode(*tree.root);
}

int nodeDepth(node_t *node){
  int t = 0;
  if(node){
      int l = nodeDepth(node->left);
      int r = nodeDepth(node->right);
    t = 1 + ((l>r)?l:r);
  }
  return t;
}
int treeDepth(tree_t tree){
  return nodeDepth(tree.root);
}

int nodeEndNodeCount(node_t *node){
  int t = 0, l = 0, r = 0;
  if(node){
    if(!node->left && !node->right)
      return 1;
    else{
	l = nodeEndNodeCount(node->left);
	r = nodeEndNodeCount(node->right);
    }
    t = l + r;
  }
  return t;
}

int endNodeCount(tree_t tree){
  return nodeEndNodeCount(tree.root);
}

int nodeContainsN(node_t *node, int n){
  if(node){
    if(node->val == n)
      return 1;
    else
      return nodeContainsN(node->left, n) + nodeContainsN(node->right, n);
  }
  return 0;
}

int treeContainsN(tree_t tree, int n){
  return nodeContainsN(tree.root, n);
}

int nodeNodeCount(node_t *node){
  int t = 0;
  if(node)
    t = 1 + nodeNodeCount(node->left) + nodeNodeCount(node->right);
  return t;
}

int nodeCount(tree_t tree){
  return nodeNodeCount(tree.root);
}

void putNodeInArray(node_t *node, int *array, int *i){
  if(node){
    array = realloc(array, ((*i)+1)*sizeof(int));
    array[*i] = node->val;
    (*i)++;
    putNodeInArray(node->left, array, i);
    putNodeInArray(node->right, array, i);
  }
}
int putTreeInArray(tree_t tree, int *array){
  int i = 0;
  putNodeInArray(tree.root, array, &i);
  return i;
}

void sortArray(int *array, int len){
  int sorted = 0;
  while(!sorted){
    int changes = 0;
    for(int i = 0; i < len-1; i++){
      if(array[i] > array[i+1]){
	changes++;
	array[i] += array[i+1];
	array[i+1] = array[i] - array[i+1];
	array[i] -= array[i+1];
      }
    }
    if(!changes)
      sorted = 1;
  }
}

void insertInNode(node_t *node, int *array, int *i){
  if(node->left)
    insertInNode(node->left, array, i);
  node->val = array[*i];
  *i += 1;
  if(node->right)
    insertInNode(node->right, array, i);
}

void insertInTree(tree_t *tree, int *array){
  int i = 0;
  insertInNode(tree->root, array, &i);
}

void sortTree(tree_t *tree){
  int *numbers = malloc(1*sizeof(int));
  int t = putTreeInArray(*tree, numbers);
  sortArray(numbers, t);
  insertInTree(tree, numbers);
  
}