CareerCup

4cases
root->left->left/right==target
root->right->left/right==target

it(T==NULL)
return;
if(T->left && T->left->left==target)
cout<<"Next largest"<<T->left->value;
else if(T->left && T->left->right==target)
cout<<"Next largest"<<T->value;
else if(T->right && T->right->left==target)
cout<<"Next largest"<<T->right->value;
else if(T->right && T->right->right==target)
cout<<"Next largest"<<T->value;
else
func(T->left,target);
func(T->right,target);

logan: tree is not BST

We can do an inorder traversal as follows:

Node GetNextLargest(Node* node)
{
	if(NULL==node)
		return NULL;
	if(node->right)
	{
		node=node->right;
		if(node->left)
			node=(node->left);
	}
	if(node->parent)
	{
		if(node==node->parent->left)
			return (node->parent);
		else 
		{
			while(node->parent)
			{
				if(node==node->parent->left)
					return node->parent;
				else 
					node=node->parent;
			}
		}
	}
	return NULL;
}

If the given tree is a BST then the second solution posted above is right. But since it has just been provided as a Binary tree i dont think we can use that solution.
@Laks: Inorder traversal is just a method of printing out nodes, since we can assume the Binary tree to be ordered in any particular manner.. i dont think simply doing a inorder traversal would give the result.
A brute force approach i can think of ;)
- Do a traversal and store the values of all nodes in an array - O(n)
- Find the next higher element by making a one pass through the array-
O(n)
Val : = value of node given to us .. whose higher noder we have to find
Big : value of the next bigger node set to 0
for( i from 1 to n)
{
if (array[i] > Val)
{
if(array[i] < Big)
Big = array[i]
}
}
- Traverse the tree looking for the node having the value of Big and return O(n)

Maybe the whole thing can be accomplished by 2 Traversals too minus the temp array
Do a traversal and find value of Big
Do a traversal and get node corresponding to Big

Inorder search the tree.
VAL current next largest value.
If node->value > GIVEN_VALUE && less than VAL
VAL = node->value;
return VAL;

Using any of the traversal algorithms, keep track of max1 and max2 (max1 = maximum node in the tree).

When you encounter a new node, you compare it with max1 first, and if the node is bigger you move max1 to max2. Or if it's smaller, compare it with max2 also.
Here is my implementation.

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
 
/*Function protoypes*/
void printGivenLevel(struct node* root, int level, int *max1, int *max2);
int height(struct node* node);
struct node* newNode(int data);
 
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
  int h = height(root);
  int i,max1=0,max2=0;
  for(i=1; i<=h; i++)
    printGivenLevel(root, i,&max1,&max2);
    
    printf("max 1 :%d, max2 :%d",max1,max2);
}     
 
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level, int *max1, int *max2)
{
  
  if(root == NULL)
    return;
  if(level == 1)
    {
    	printf("%d ", root->data);
    	
    	if(root->data > *max1)
    		{
    			*max2 = *max1;
    			*max1 = root->data;
    		}
    	else if(root->data > *max2)
    	*max2 = root->data;
    	
    }
   
  else if (level > 1)
  {
    printGivenLevel(root->left, level-1,max1,max2);
    printGivenLevel(root->right, level-1,max1,max2);
  }
}
 
/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
     /* compute the height of each subtree */
     int lheight = height(node->left);
     int rheight = height(node->right);
 
     /* use the larger one */
     if (lheight > rheight)
         return(lheight+1);
     else return(rheight+1);
   }
} 
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
 
  return(node);
}
 
/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(100);
  root->left        = newNode(21);
  root->right       = newNode(32);
  root->left->left  = newNode(4);
  root->left->right = newNode(5); 
 
  printf("Level Order traversal of binary tree is \n");
  printLevelOrder(root);
 
  getchar();
  return 0;
}

To find the next largest node look at the right subtree of the node. The leftmost leaf in the right subtree will be the next successor (or the next largest node). If there is no right subtree then move up till the current node is left child of it's parent, the parent then forms the next successor.

Can we do an inorder traversal of the tree and look for the node with the given value. The node that is after printed this node is the next largetst node since an inorder traversal gives us a sorted list.
Let me know if this is possible.