#ifndef _BST_
#define _BST_
 
struct Tree_Node 
{
    int value;
    struct Tree_Node *leftNode;
    struct Tree_Node *rightNode;
};
 
struct BST
{
    struct Tree_Node *root;
};

// -----------------Tree Node Function---------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *);
void Tree_Node_Deallocate(struct Tree_Node *);



struct BST* BST_Allocate(struct BST *BST)
{
    BST = malloc(sizeof(struct BST));
    assert(BST != 0);
    BST->root = NULL;
 
    return BST;
}
// -----------------------------------------------------------
int* BST_Deallocate(struct BST *BST, int *isBST_De_allocate)
{
	// Memory Leak if i only delete root and not
    // all tree nodes request from heap memory
	/*
		Use postorder traversal method to free Tree Node
		and finally root
	*/

    if (BST != NULL && BST->root != NULL)
    {
		if (*isBST_De_allocate == 0)
		{
			RecursivePostOrder_Deallocate(BST->root);
			free(BST);
		}
    }
    else
    {
        exit(0);
    }
	
	*isBST_De_allocate = 1;

	return isBST_De_allocate;
}

#ifndef _BST_
#define _BST_
 
struct Tree_Node 
{
    int value;
    struct Tree_Node *leftNode;
    struct Tree_Node *rightNode;
};
 
struct BST
{
    struct Tree_Node *root;
};

// -----------------Tree Node Function---------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *);
void Tree_Node_Deallocate(struct Tree_Node *);
 
struct Tree_Node* Tree_Node_Initialize(struct Tree_Node *, int *);
 
struct Tree_Node* Searching(struct BST *, int *);
struct Tree_Node* RecursiveSearch(struct Tree_Node *, int *, ...);
struct Tree_Node* RecursiveMinSearch(struct Tree_Node *);
struct Tree_Node* RecursiveMaxSearch(struct Tree_Node *);

// --------------------------------------------------------------

// ------------------BST Tree Function---------------------------
struct BST* BST_Allocate(struct BST *);
int* BST_Deallocate(struct BST *, int *);
 
struct BST* BST_Insert(struct BST *, struct Tree_Node *);
struct BST* BST_Remove(struct BST *,int *); 

void FindMin(struct BST *);
void FindMax(struct BST *);
void MinHeight(int *);
void MaxHeight(int *);

void BST_UserInput(int *);
int* QuerySearchValue(int *);
int* numberTreeNodes(int *);
int* removeNode(int *);

// Root->Left->Right
/*
	If left node has children, traversal down until left
	has no children
	Or called Depth-First Traversal(DFS)
*/
void PreorderDisplay(struct BST *);  
void RecursivePreorderDisplay(struct Tree_Node *);

// Left->Root->Right
void InorderDisplay(struct BST *);
void RecursiveInorderDisplay(struct Tree_Node *);

// Left->Right->Root
void PostorderDisplay(struct BST *);
void RecursivePostorderDisplay(struct Tree_Node *);
/*
	Breadth-first traversal(BFS) - traversal from level 0 
	until lowest level
*/
void RecursivePostOrder_Deallocate(struct Tree_Node *);
void SearchDisplay(struct Tree_Node *, int *);

// --------------------------------------------------------------

#endif
/*
	Binary Search Tree can be used for efficient searching, 
	arithmetic expression parsing, and 
	data compression

	Fullness - Previous Level * 2 = Current Level is 
			   consider fullness
	Balance - isBalanced() - Find Maximum height
	          of left node and right node
			  if == balanced else unbalaced
			  All node must same height then 
			  considered balanced
	Leftness - 

    Recursion good for keeping track of paths(Fixed Path or a route)

	AVL Tree - Tree that help balancing when inserted
	Splay Tree - Move data that frequent accessed to
				 the top of tree
    Heap - Another sorted tree structure used maily
	       in priority queue
	Huffman Tree - Used for data compression
    
*/