tree search algorithm (cont.)

 The previous post is here
============
struct treeNode{
    int element;
    struct treeNode *left;
    struct treeNode *right;
}:
typedef struct treeNode *searchTree;


searchTree makeEmpty(searchTree T){
    if(T!=NULL){
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}


searchTree findVal(int val, searchTree T){
    if(T==NULL)
        return NULL;
    if(valelement)
        return findVal(val, T->left);
    else if(val>T->element)
        return findVal(val, T->right);
    else
        return T;
}


searchTree findMin(searchTree T){
    if(T!=NULL)
        while(T->left!=NULL)
            T = T->left;
    return T;
}


searchTree insertVal(int val, searchTree T){
    if(T==NULL){
        T=(searchTree)malloc(sizeof(struct treeNode));
        if(T==NULL){
            printf("Error! There is no new memory to allocate.\n");
            exit(0);
        }
        T->element = val;
        T->left = T->right = NULL;
    }
    else{
        if(valelement)
            T->left = insertVal(val, T->left);
        else if(val>T->element)
            T->right = insertVal(val, T->right);
        else
            printf("The element has already in this tree.\n");
    }
    return T;
}


searchTree deleteVal( int val, searchTree T){
    searchTree temp;
    if(T==NULL){
        printf("The element is not found.\n");
        return NULL;
    }
    else if(valelement)
        T->left = deleteVal(val, T->left);
    else if(val>T->element)
        T->right = deleteVal(val, T->right);
    else{        // here, find the specific element
        if(T->left && T->right){
            temp = findMin(T->right);
            T->element = tmp->element;
            T->right = deleteVal(tmp->element, T->right);
        }
        else{
            temp = T;
            if(T->left == NULL)
                T = T->right;
            else if(T->right==NULL)
                T = T->left;
            free(temp);
        }
        return T;
    }
}

// the functions below returns node which element is closest
// and larger in the Tree. We could call it "next"
// assumption1: the inputs are inquiry val and the root node
searchTree nextLarger(int val, searchTree T){
    searchTree temp;
    if(T==NULL){
        printf("There is no tree.\n");
        return NULL;
    }
    if(valelement){
        if(T->left!=NULL){
            temp = T->left;
            while(valelement && temp->left!=NULL){
                T = temp;
                temp = temp->left;
            }
            // This case indicate "temp->left==NULL" causes stop
            // so temp should be the return value
            if(valelement)
                T = temp;
            // otherwise, result might in a new right tree
            // . or the parent node in this layer
            else{
                if (temp->right!=NULL){
                    temp = nextLarger(val, temp->right);
                    if (temp!=NULL)
                        T = temp;
                }
            }
        }
        return T;
    }
    else{
        while(val>=T->element && T->right!=NULL)
            T = T->right;
        if(valelement){
            T = nextLarger(val, T);
            return T;
        }
        else
            return NULL;
    }
}


// assumption2: the input value is a given node in the tree.
// In this case, we might have to trace back.
// As a resutl, the original struct needs a little modification
struct treeNode{
    int element;
    struct treeNode *left;
    struct treeNode *right;
    struct treeNode *parenet;    // to trace back
}:
typedef struct treeNode *searchTree;

searchTree nextLarger2(searchTree start){
    searchTree temp, record;
    if(start==NULL){
        printf("There is not a valid input.\n");
        return NULL;
    }
   
    if(start->right!=NULL){
        start = findMin(start->right);
        return start;
    }
    else if(start->parent!=NULL){
        if(start == start->parent->left)
            return start;
        else{
            while(start->parent!=NULL && start!=start->parent->left)
                start = start->parent;
            if(start==start->parent->left)
                return start;
            else
                return NULL;
        }
    }
}


// references: <Introduction to algorithms>, <Coding Interviews>

// I just did some terrible interviews these days. Yes, some, and terrible.
// So, I wanna record everything here, 
// no matter how stupid and rudimentary it is.
// Also as a means to push myself, everyday a step further.