/*
 * 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;

/////////////////////////////////////////////////
// Stack implementation
#define SIZE 100

typedef struct {
	Node* data[SIZE];
	int top;    // 0 represent empty stack
} Stack;

void push(Stack* s, Node* data) {
	if (s->top == SIZE - 1) {
		fprintf(stderr, "overflow!\n");
		exit(1);
	}
	s->data[s->top++] = data;
}

Node* pop(Stack* s) {
	if (s->top == 0) {
		fprintf(stderr, "underflow!\n");
		exit(1);
	}
	return s->data[--s->top];
}

void init(Stack* s) {
	s->top = 0;
}

Node* top(Stack* s) {
	return s->data[s->top - 1];
}

int empty(Stack* s) {
	return s->top == 0;
}
//////////////////////////////////////////////////////

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) {
	Node* p = root;
	Node* temp;
	Stack s;
	init(&s);

//	push(&s, p);
	while (1) {
		if(p->left) {
			push(&s, p);
			p = p->left;
		} else {
			printf("%d ", p->key);

			if (p->right) {
				p = p->right;
			} else {
				// keep poping till find node has right
				temp = pop(&s);
				printf("%d ", temp->key);
				while (!temp->right && !empty(&s)) {
					temp = pop(&s);
					printf("%d ", temp->key);
				}
				p = temp->right;
			}
		}
		if(empty(&s) && p==NULL) break;
	}
}

void inorder_walk_stack2(Node* root) {
	Node* p = root;
	Stack s;
	init(&s);

	while(1) {
		if(p) {
			push(&s, p);
			p = p->left;
		} else if (!empty(&s)) {
			p = pop(&s);
			printf("%d ", p->key);
			p = p->right;
		} else
			break;
	}
}

/* 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_iterative(root, 4);
	root = insert_recursive(root, 3);
	root = insert_recursive(root, 9);
	root = insert_recursive(root, 8);
	root = insert_recursive(root, 2);
	inorder_walk_recursive(root);
	printf("\n");
	inorder_walk_stack(root);
	printf("\n");
	inorder_walk_stack2(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;
}