CareerCup

My solution in O(logn) [ Using Predecessor & Sucessor concept ] :

node *find_closest(node *root, int x)
{
    static node *pre = NULL, *suc = NULL;
    
    node *result = NULL;
    
    if(root != NULL)
    {
        if(root -> data > x)
        {
            if(suc == NULL)
                suc = root;
            else if(suc -> data > root -> data)
                suc = root;
            
            result = find_closest(root -> left, x);
        }
        else if(root -> data < x)
        {
            if(pre == NULL)
                pre = root;
            else if(pre -> data < root -> data)
                pre = root;
            
            result = find_closest(root -> right, x);
          }
        else
            result = root;
        
        if(result == NULL)
        {
            if(pre != NULL && suc != NULL)
            {
                if((x - pre -> data) < (suc -> data - x))
                    result = pre;
                else
                    result = suc;
            }
            else 
            {
                if(pre == NULL)
                    result = suc;
                else
                    result = pre;
            }
        }
            
    }
    
    return result;
}

// how to call the function, we know the root and specified data
TreeNode* node = NULL
FindSimilarTreeNode(root, 100, node);

// Find the node whose value is closest to the spcified data.
void FindSimilarTreeNode(TreeNode *current, const int ele, TreeNode *findedNode)
{
    if (!current) 
        return;

    if (!findedNode)
    {
        if (abs(current->data - ele) < abs(findedNode->data - ele))
        {   
            // current->data is nearer to ele
            findedNode = current;

            if (current->data > ele)
            {
                FindSimilarTreeNode(current->left, ele, findedNode);
            }
            else
            {
                FindSimilarTreeNode(current->right, ele, findedNode);
            }

        }
        else 
        {
            // the algorithm is that the abs() value should be smaller, 
            // if we find that the abs() is bigger, which means the current "findedNode" is closest node 
            return;
        }
    }
    else
    {
        findedNode = current;

        if (current->data > ele)
        {
            FindSimilarTreeNode(current->left, ele, findedNode);
        }
        else
        {
            FindSimilarTreeNode(current->right, ele, findedNode);
        }
    }
}

static TreeNode findClosest(TreeNode root,int x){
if(root == null)
return null;
int diff = Math.abs(root.data -x);
TreeNode close = root;
TreeNode leftClosest = findClosest(root.left,x);
TreeNode rightClosest = findClosest(root.right,x);
if(leftClosest!=null){
int diffleft = Math.abs(leftClosest.data - x);
if(diffleft < diff){
close = leftClosest;
diff= diffleft;
}
}

if(rightClosest!=null){
int diffright = Math.abs(rightClosest.data - x);
if(diffright < diff){
close = rightClosest;
diff= diffright;
}
}
return close;
}

can I just insert this value, then if the value is a right-child, then find its predecessor;if it is a left-child, then find its successor, finally compare the abs(its parent-itself) and abs(its predecessor/successor-itself).
insert, predecessor and successor are all standard interface for BST and take lgn time.

function: TreeNode findClosest(TreeNode root,int x){
Do binary search.
keep following variables:
gtNode: will keep node information, from which x was found greater.
ltNode: will keep node information, from which x was found smaller.
As we proceed, we shall keep updating these variables with condition that,
1. gtNode will be updated only if candidate gtNode has smaller difference then existing one.
2. ltNode will be updated only if the candidate ltNode has smaller difference then existing one.
The search will stop as soon as 1 or 2 gets violated or you reach end of tree.
compare gtNode and ltNode for closest match and that will be the result.

class Node {
    public:
        int key;
        Node* left;
        Node* right;
};

class Tree {
    public:
        public root;
        Node* search(Node* node, int key) {
            Node* temp = node;
            while (temp != NULL && temp.key != key) {
                if (temp.key > key) {
                    temp = temp.left;
                } else {
                    temp = temp.right;
                }
            }
            return temp;
        }

        Node* searchClosest(Node* node, int key) {
            Node* high = NULL;
            Node* low = NULL;
            Node* temp = node;
            while (temp != NULL && temp.key != key) {
                if (temp.key > key) {
                    high = temp;
                    temp = temp.left;
                } else {
                    low = temp;
                    temp = temp.right;
                }
            }
            if (temp != NULL && temp.key == key) {
                return temp;
            }
            Node* closest = low;
            if (high != NULL) {
                if (closest == NULL) {
                    closest = high;
                } else if (high.key - key < key - closest.key) {
                    closest = low;
                }
            }
            return closest;
        }
};

static BinaryNode findClosestNode(BinaryNode root,int value){
		int min = Integer.MAX_VALUE;
		BinaryNode cn = null;
		while(true){
			if(root == null) return cn;
			if(root.value == value){
					return root;
			}else if(root.value > value){
				if(min > Math.abs(root.value - value)){
					min = Math.abs(root.value - value);
					cn = root;
				}
				root = root.left;
			}else{
				if(min > Math.abs(root.value - value)){
					min = Math.abs(root.value - value);
					cn = root;
				}
				root = root.right;
			}
		}

will this work? (log n running time)

Finding a node in BST
We will exploit BST's property that left sub tree contains elements which are smaller that the parent key and Right sub tree contains the elements which are greater than the parent key.

Node find(Node n , int x)
{
if(n == null)
return;
if(n.val == x)
return n;
if(n.val < x)
find (n.right, x)
else
find (n.left, x)

}

}