//
// find whether a node exists in a Binary Search Tree
// and if it does not exist, then return the Successor
// if successor also does not exist, return NULL
// - Gaurang Khetan [ http://gaurang.org/programs ]

#include <stdio.h>

struct Node 
{
    Node* left;
    Node* right;
    int value;
};

Node* new_node(int value)
{
    Node* newnode = new Node;
    newnode->value = value;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

Node* find_recurse(Node* node, int value)
{
    Node* ret_node;
    
    if (value == node->value)
        return node;

    if (value < node->value)
        {
            if (node->left == NULL)
                return node; //return ourself; since we are the successor of this non-existent child

            ret_node = find_recurse(node->left, value);

            if (ret_node != NULL)
                return ret_node; 
            else
                return node;  //it is NULL means it is non-existent; but we ARE the successor 
        }            
    else /* value > node->value */
        {
            if (node->right == NULL)
                return NULL;

            // here we dont treat NULL return as a special case, 
            // since we are looking at the right child, so we are not the successor
            // if we get NULL, we pass on the NULL!
            ret_node = find_recurse(node->right, value);

            if (ret_node != NULL)
                return ret_node; 
            else
                return NULL;  //it is NULL means it is non-existent; but we ARE NOT the successor
        }            
}

// the parent function
Node* find(Node* root, int value)
{
    if (root == NULL) 
        return NULL;

    return find_recurse(root, value);
}

//insert a node into a binary tree
void insert(Node* node, int value)
{
    if (value < node->value)
        {
            if (node->left == NULL)
                node->left = new_node(value);
            else
                insert(node->left, value);
        }
    else // duplicates will fall in here too
        {
            if (node->right == NULL)
                node->right = new_node(value);
            else
                insert(node->right, value);
        }
}

//convenience function
void insert_into_tree(Node* node, int value)
{
    printf("\n Inserting into tree value %d... ", value);
    insert(node, value);
    printf("done.");
}

//convenience function
void searchfor(Node* node, int value)
{
    printf ("Searching for value=%d...", value);
    
    Node* ret_node = find(node, value);

    if (ret_node == NULL)
        printf(" Value returned: NULL\n");
    else
        printf(" Value returned: %d\n", ret_node->value);
}

int main()
{
    // make a tree here
    printf("\n Starting the tree with root 40.\n");
    Node* root = new_node(40);
    insert_into_tree(root, 20);
    insert_into_tree(root, 60);
    insert_into_tree(root, 10);
    insert_into_tree(root, 30);
    insert_into_tree(root, 80);
    insert_into_tree(root, 25);
    insert_into_tree(root, 35);
    insert_into_tree(root, 27);

    //get answers for some default values
    printf("\n\nSearching for some default values...\n\n");
    searchfor(root,9);
    searchfor(root,20);
    searchfor(root,26);
    searchfor(root,28);
    searchfor(root,36);
    searchfor(root,90);

    // get values from the user to search for
    printf("\n\nNow its open for you to query...\n");
    while(1)
        {
            int value;

            printf("\n What value to search(0 to exit): ");
            scanf("%d", &value);

            if (value == 0) //to break, give 0
                break;

            searchfor(root, value);
        }

    return 0;
}