/*
 * This file demonstrates basic functions
 * for binary search tree (BST)
 */

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

typedef struct Node{
  int key;
  struct Node *left;
  struct Node *right;
}Node;

Node* search_recursive(Node* root, int key) {
  if(root==NULL) 
	return NULL; // not found
  else if(root->key==key)
	return root;
  else if(root->key>key)
	search_recursive(root->left, key);
  else  //  if(root->key<key)
	search_recursive(root->right, key);
}

Node* search_iterative(Node* root, int key) {
  Node* cur = root;
  while(cur!=NULL) {
	if(cur->key==key)
	  return cur;
	if(cur->key>key)
	  cur = cur->left;
	else
	  cur = cur->right;
  }
  return NULL; // not found
}

Node* insert_recursive(Node* root, int key) {
  if (root==NULL) {
	// find insert position, create new node
	root = (Node*) malloc(sizeof(Node));
	root->key = key;
	root->left = NULL;
	root->right = NULL;
	
	return root; // if return void, you need to use parameter pass by address
  } 

  // here we ignore duplicate key case  
  if(root->key>key) 
	root->left = insert_recursive(root->left, key);
  else
	root->right = insert_recursive(root->right, key);

  return root;
}

Node* insert_iterative(Node* root, int key) {

  // create new node
  Node* temp = (Node*) malloc(sizeof(Node));
  temp->key = key;
  temp->left = NULL;
  temp->right = NULL;

  if (root==NULL) { root = temp; return root; } // trivial case

  Node* cur = root;
  Node* p = NULL;
  while(cur!=NULL) {
	p = cur;	
	if(cur->key>key)
	  cur = cur->left;
	else 
	  cur = cur->right;
  }

  if(p->key>key)
	p->left = temp;
  else
	p->right = temp;
  
  return root;
}

// implement in project 2
Node* delete_iterative(Node* node){
  return;
}

Node* successor(Node* node){
  return;
}


void inorder_walk_recursive(Node* root) {
  if (root==NULL) return;
  inorder_walk_recursive(root->left);
  printf("%d ", root->key);
  inorder_walk_recursive(root->right);
}

void inorder_walk_stack(Node* root) {
  
}

/* free tree node using postorder */
void free_tree(Node* root) {
  if (root==NULL) return;
  free_tree(root->left);
  free_tree(root->right);
  free(root);
}

int main () {

  Node* root = NULL;
  Node* temp = NULL;
  root = insert_recursive(root, 3);
  root = insert_recursive(root, 8);
  root = insert_iterative(root, 4);
  root = insert_recursive(root, 9);  
  root = insert_recursive(root, 2); 
  inorder_walk_recursive(root);
  printf("\n");

  temp = search_iterative(root, 3);
  if (temp==NULL)
	printf("not found\n");
  else
	printf("found key\n");


  free_tree(root);
  
  return 0;
}