CareerCup

void findNext(Node *root,int target){
    public static Node * prev = NULL;
    if(root == NULL)
        return;
    else{
        findNext(root->left,target);
        if(prev != NULL){
            if(prev -> value == target && prev->value < root->value){
                printf("%d",root->value);
        prev = root;    
        findNext(root->right,target);
    }
}

tree* searchLeftmostnodeInRightSubtree (tree* root)
{
        while (root->left)
        {
                root = root->left;
        }
        return root;
}

tree* inorderSuccessor (tree *root, int key)
{
        if (root)
        {
                if (root->key == key)
                {
                        /*inorder successor will be in right subtree of node if right subtree exist*/
                        if (root->right)
                        {
                                tree *subtree = searchLeftmostnodeInRightSubtree(root->right);
                                return subtree;
                        }
                        /*If right subtree of this node doesnot exist, then parent node for which leftsubtree consist this node*/
                        else
                        {
                                return root;
                        }
                }
                tree *left = inorderSuccessor (root->left, key);
                if (left)
                {
                        /*if immediate child is key*/
                        if (left->key == key)
                        {
                                return root;
                        }
                        /*tree is returning correct value*/
                        return left;
                }
                tree *right = inorderSuccessor (root->right, key);
                return right;
        }
        return NULL;
}

int floor(int val, node x)
{
	if(x==null)
		return null
	if(val>=x.val)
	{
		a = floor(val, x.right)
		if(a==null)
			return x.val
	}
	else
	{
		return floor(val, x.left)
	}
}

Logic:
There can be three possibilities:
1. There is only one element in the tree
2. The key element is the left node of it's parent node
3. The key element is the right node of it's parent node

Approach:
For case one there can be no result possible
For case two parent of key node is the next larger element
For case three parent of parent is the next larger element

Sol:
Perform binary search on the tree to search key element just make sure you are keeping parent and parent's parent in temp var for current node while traversing tree

Time Complexity: nlog(n)
Space Complexity: (2 * logn)

Ask how the BST is provided to you
1. If provided as 2 arrays (inorder and preorder) then binary search for element in inorder array and return next element. check for appropriate boundary conditions
2. If provided as object and pointers, assume a node also saves its parent in addition to left and right for convenience:

public abstract class BST<T>
	{
		//Implement binary search
		public abstract Node<T> findNodeUsingBinarySearch(Node<T> root, T targetValue);
		
		public T findInorderSuccessor(Node<T> root, T targetValue)
		{
			Node<T> target =  findNodeUsingBinarySearch(root, targetValue);
			if(target != null)
			{
				if(target.getRight() != null)
				{
					return target.getRight().getData();
				}
				else
				{
					Node<T> successor = findAncestor(target.getParent(), target);
					if(successor != null)
					{
						return successor.getData();
					}
					else
					{
						//last element
					}	
				}
			}
			else
			{
				throw new ElementNotFoundException();
			}
		}

		//find ancestor such that target is in left subtree of the ancestor
		public Node<T> findAncestor(Node<T> parent, Node<T> child)
		{
			if(parent != null)
			{
				if(parent.getLeft().equals(child))
				{
					return parent;
				}
				else
				{
					return findAncestor(parent.getParent(), parent);
				}
			}
			return parent;
		}
	}

static boolean flag=false;
public static void inOrder(TreeNode root,int judge){
if(root!=null){
inOrder(root.left,judge);
if(flag) {
System.out.println(root.data);
flag=false;
}
if(root.data==judge) flag=true;

inOrder(root.right,judge);
}
}

t4.left=t3;t4.right=t5;
t3.left=t1;t3.right=t2;
t5.right=t7;t7.right=t6;
Integer judge=10;
inOrder(t4, judge);

I think this is equivalent to the problem of returning the left-most node in the sub-tree with elements greater than the value provided. Here's my attempt to solve it:

TreeNode* find_next_higher(TreeNode* root, const int& value)
{
    if (root == NULL)
        return NULL;

    if (root->left != NULL && root->left->value > value)
        return find_next_higher(root->left, value);

    if (root->value > value)
        return root;

    if (root->right != NULL)
        return find_next_higher(root->right, value);

    return NULL;

}

The leftmost node of right subtree

The following should work (code has comments):

public static Integer find(Node root, int n) {
  if (root == null) {
    // invalid, return max int
    return Integer.MAX_VALUE;
  }
  if (root.v <= n) {
    // solution is in the right branch
    return find(root.right, n);
  } else {
    // solution is either the current node or the max found in the left tree
    // we choose the minimum of the two to find the 'closer' largest value
    return Math.min(root.v, find(root.left, n));
  }
}

Running time is O( lg N ).

What is the given input type ?
1) Is it preorder of the binary tree and the node value of which we need to find its successor?
or
2) root of the BST and the node value of which we need to find its successor

public int getNextLargestValue(Node root, int target) {
if(root == null) {
return -1;
}
if(root.val < target) {
return getNextLargestValue(root.right, target);
} else {
if(root.left == null) {
if(root.val != target) {
return root.val;
}
return -1;
} else {
int val = getNextLargestValue(root.left, target);
return val == -1 ? root.val > target ? root.val : -1
: val;
}
}

}

public int getNextLargestValue(Node root, int target) {
         if(root == null) {
             return -1;
         }
         if(root.val < target) {
             return getNextLargestValue(root.right, target);
         } else {
             if(root.left == null) {
                 if(root.val != target) {
                     return root.val;
                 }
                 return -1;
             } else {
                 int val = getNextLargestValue(root.left, target);
                 return val == -1 ? root.val > target ? root.val : -1
                                : val;
             }
         }
         
     }

Do an inorder traversal of the tree. The values will be in ascending order. Then do a binary search on resulting array to find the index of given number, and then find the next highest number in constant time.

public bool Search(Node Root, int T, ref Node P)
{
if(Root==null) return;

Node C = Root;

while(C!=null);
{
if(C!=null)
{
if(C.left==null)
{
if(C.Val>T && P==null)
{
P=C; return true;
}
C=C.Right;
}
else
{
Node R = C.Left;
while(R.Right!=null && R.Val!=C.Val)
{
R=R.Right;
}
if(R.Right==null)
{
R.Right=C;
C=C.Left;
}
else
{
R.Right=null;
if(C.Val>T && P==null)
{
P=C; return true;
}
C=C.Right;
}
}
}
}
return false;
}

Do inorder traversal till you find first higher value then n - 9.

public static Integer find(Node root, int n) {

	if (root == null) {
	    return null;
	}
	Integer result = null;
	result = find(root.left, n);
	if (root.v <= n) {
	    result = find(root.right, n);
	} else {
	    return root.v;
	}

	return result;
}

only need to find its successor.

a

Do inorder traversal till you find first higher value then n - 9.

public static Integer find(Node root, int n) {

	if (root == null) {
	    return null;
	}
	Integer result = null;
	result = find(root.left, n);
	if (root.v <= n) {
	    result = find(root.right, n);
	} else {
	    return root.v;
	}

	return result;
}