/**
 * @file binary_search_tree.cpp
 * @author Shirish Reddy <shirishreddy89@gmail.com>
 *
 * Binary search tree along with the dynamic set operations of insert, delete,
 * predecessor, successor, minimum, maximum.
 */



#include <iostream>

using namespace std;

/**
 * structure defining the node of Binary search tree
 * each node has link to left child, right child, parent and the key data
 */
struct node {
	node *left, *right, *p;
	int key;
};

node* tree_successor(node* x);
node* tree_predecessor(node* x);

/**
 * tree_insert - inserts the node 
 */
void tree_insert (node **T, node *z)
{
	node *y = NULL;
	node *x = *T;
	while (x != NULL) {
		y = x;
		if(z->key < x->key) 
			x = x->left;
		else
			x = x->right;
	}
	z->p = y;
	if (y == NULL){
		*T = z;
	}
	else {
		if (z->key < y->key)
			y->left = z;
		else
			y->right = z;
	}
}


/**
 * tree_delete - deletes a node in the tree in O(h) time
 * three cases arise where the node to be deleted is a leaf
 * node to be deleted has one child
 * node to be deleted has two children
 *
 */
node* tree_delete(node** T, node *x)
{
	node *y, *z;
	if(x->left == NULL || x->right == NULL)
		y = x;				//if either of nodes or both nodes are null 	
	else
		y = tree_successor(x);		//None of the right or left nodes are null 	
	if (y->left !=NULL)
		z = y->left;		
	else
		z = y->right;
	if (z!=NULL)				//if the right or left child is present for node 'y'
		z->p = y->p;
	if(y->p == NULL)			//if y is a root node
		*T = z;				
	else {
		if( y == y->p->left)		//reconstructing links
			y->p->left = z;
		else
			y->p->right = z;
	}
	if(y!=x)
	 	x->key = y->key;
	return y;
}

/**
 * QUERYING A BINARY SEARCH TREE
 */
 
/**
 * tree_search take O(h) time to search for a key where 'h' is height of the tree
 */
node* tree_search(node* T, int k)
{
	node *x = T;
	if( x == NULL || x->key == k)
		return x;
	if (k < x->key)
		return tree_search(x->left, k);
	else
		return tree_search(x->right, k);
}
/**
 * iterative_tree_search , searches for the key iteratively
 */
node* iterative_tree_search(node* T, int k) 
{
	node* x = T;
	while(x!=NULL && k != x->key){
		if(k < x->key)
			x = x->left;
		else 
			x = x->right;
	} 
	return x;
}

/**
 * tree_mininum - finds the minimum value reccursively
 */
node* tree_minimum(node* T)
{
	while(T->left!=NULL)
		 T = tree_minimum(T->left);
	return T;
}

/**
 * tree_maximum
 */
node* tree_maximum(node* T)
{
	while(T->right != NULL)
		T = T->right;
	return T;
}

/**
 * tree_successor - searches for the successor of a node in O(h) time
 * successor is generally the minimum of the right subtree where the elements are > root
 * when no right subtree is present and it satisfies the below if condition then the parent might be the predecessor
 */
node* tree_successor(node* x)
{
	if( x->right != NULL)			//search the minimum of right subtree to find the successor
		return tree_minimum(x->right);
		
	node* y = x->p;			//if no right subtree then search in the parent's right subtree			
	while( y != NULL && x == y->right) {
		x = y;
		y = y->p;
	} 
	return y;
}

/**
 * tree_predecessor 
 * predecessor is generally the maximum of left subtree where the elements are < root
 * when no left subtree is present and it satisfies the below if condition then the parent might be the predecessor
 */
node* tree_predecessor(node* x)
{
	if(x->left != NULL)
		return tree_maximum(x->left);
	node* y = x->p;
	while( y != NULL && x == y->left) {
		x = y;
		y = y->p;
	}
	return y;
}
node* make_tree(node *z)
{
	z->left = NULL;
	z->right = NULL;
	z->p = NULL;
	return z;
}
int main()
{
	node* T = NULL;
		
	node* z = new node;
	z->key = 12;
	tree_insert(&T, z);
	node* z1 = new node;
	z1->key = 26;
	tree_insert(&T, z1);
	node* z2 = new node;
	z2->key = 112;
	tree_insert(&T, z2);
	node* z3 = new node;
	z3->key = 1212;
	tree_insert(&T, z3);
	node* z4 = new node;
	z4->key = 212;
	tree_insert(&T, z4);
	cout<<T->right->right->right->left->key;
	cout<<tree_predecessor(tree_successor(z))->key;
	delete z;
	delete z1;
	delete z2;
	delete z3;
	delete z4;
	return 0;
}

Segmentation fault