// Tree.h                                           Stan Eisenstat (04/01/16)
//
// Specification of the interface for a Tree ADT that stores unique (Key,Attr)
// pairs in a binary search tree ordered by Key.

#include <stdbool.h>

typedef struct tree *Tree;      // External definition of Tree
typedef int Key, Attr;          // Datatypes for Key and Attr

// Search for Key K in Tree T.  If found, then put corresponding Attr in *A
// and return TRUE, else return FALSE.
bool search (Tree t, Key k, Attr *a);

// Insert pair (K,A) into Tree T if no pair with Key K is already present;
// otherwise replace Attr field corresponding to Key K by A.  Return pointer
// to updated Tree.
Tree insert (Tree t, Key k, Attr a);

// Delete pair with Key K from Tree T.  Return pointer to updated tree.
Tree delete (Tree t, Key k);

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// Tree.c                                           Stan Eisenstat (04/01/16)
//
// A rough, incomplete, and untested implementation of the Tree ADT.

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

struct tree {               // Internal definition of the Tree ADT
    Key key;                //  Each node contains a (Key, Attr) pair
    Attr attr;
    Tree left, right;       //  Each node has a left and a right subtree
};


// Search for Key K in Tree T.  If found, then put corresponding Attr in *A
// and return TRUE, else return FALSE.
bool search (Tree t, Key k, Attr *a)
{
#ifdef RECURSIVE                                // Recursive version
    if (t) {
	if (k < t->key)
	    return search (t->left, k, a);      // Search in left subtree
	else if (t->key < k)
	    return search (t->right, k, a);     // Search in right subtree
	else {
	    *a = t->attr;                       // Found
	    return true;
	}
    }
#else                                           // Iterative version
    while (t) {
	if (k < t->key)
	    t = t->left;                        // Move to left subtree
	else if (t->key < k)
	    t = t->right;                       // Move to right subtree
	else {
	    *a = t->attr;                       // Found
	    return true;
	}
    }
#endif

    return false;                               // Not found
}


// Insert pair (K,A) into Tree T if no pair with Key K is already present;
// otherwise replace Attr field corresponding to Key K by A.  Return pointer
// to updated Tree.
Tree insert (Tree t, Key k, Attr a)
{
    if (t) {
	if (k < t->key)
	    t->left = insert (t->left, k, a);   // Insert in left subtree
	else if (t->key < k)
	    t->right = insert (t->right, k, a); // Insert in right subtree
	else
	    t->attr = a;                        // Replace existing attribute
	return (t);                             // Return modified tree
    }

    return makenode (k, a);                     // Create single-node tree
}


// Delete node with largest key in nonempty Tree T and set *P to that node.
// Return pointer to updated tree.
static Tree deleteLargest (Tree t, Tree *p)
{
    if (t->right == NULL) {                     // No right child =>
	*p = t;                                 //   Root is largest
	return t->left;
    } else {
	t->right = deleteLargest (t->right, p); // Largest in right child
	return t;
    }
}

// Delete root of Tree T.  Return pointer to updated tree.
static Tree deleteRoot (Tree t)
{
    Tree p;                     // Modified tree

    if (t->left == NULL)                        // Case 1: No left child
	p = t->right;                           //   Promote right child
    else if (t->right == NULL)                  // Case 2: No right child
	p = t->left;                            //   Promote left child
    else {                                      // Case 3: Two children
	t->left = deleteLargest (t->left, &p);  //   Delete predecessor
	p->left = t->left;                      //   and make it new root
	p->right = t->right;
    }

    free(t);                                    // Free tree node deleted
    return p;                                   // Return modified tree
}

// Delete pair with Key K from Tree T.  Return pointer to updated tree.
Tree delete (Tree t, Key k)
{
    if (t) {
	if (k < t->key)
	    t->left = delete (t->left, k);      // Delete from left subtree
	else if (t->key < k)
	    t->right = delete (t->right, k);    // Delete from right subtree
	else
	    t = deleteRoot (t);                 // Delete key at root
    }

    return (t);                                 // Return modified tree
}