CareerCup

1. If the node has right child. then return leftmost child of the right subtree.
2. Else if node is the left child of its parent then return its parent
3. Else go up to the parent until you find a node that is a left child of its parent. Return the parent.
4. Return null

Here is the code

public TreeElement findNextLargest(TreeElement n) {
        if (n == null) {
            return null;
        }

        TreeElement parent = n.parent;
        TreeElement temp;
        if (n.right != null) {
            temp = n.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp;
        } else if (parent != null && n == parent.left) {
            return parent;
        } else {
            temp = n;
            while (parent != null) {
                if (temp == parent.left) {
                    return parent;
                }

                temp = parent;
                parent = parent.parent;
            }
        }
        return null;
    }

That's simply the inorder successor..either the leftmost child of the right child or right child or parent (in preference order, depending on existence).

why do we need a parent pointer just wondering. The next largest node will be the left most node of the right node of the given node.

in case if a node has no childrens then its parent could be the next largest. One cannot wonder in the written test for a problem statement

another 2 cases
1.if parent is same as that of given node
2.if given node has no right child and given node is right of parent then...

The function 'findNextLargest' will do the job

node* findElement(node* r,int val)
{
	if(!r)
		return NULL;

	if(r->data == val)
		return r;
	if(r->data < val)
		return findElement(r->right,val);
	else
		return findElement(r->left,val);
}
node* findMin(node* s)
{
	while(s->left)
		s = s->left;
	return s;
}
int findNextLargest(node* r,int val)
{
	if(!r || !r->right)
	{
		cout<<"No such element"<<endl;
		return ERROR_CONST;
	}
	node* s = findElement(r,val);
	if(s->right != NULL)
	{
		node* t = findMin(s->right);
		return t->data;
	}
	while(s != r)
		s = s->parent;

	if(s==r)
		return ERROR_CONST;
	
	return s->data;

}

Complexity:
Time: best case is O(1), worst case when searching left most of parent is O(n)
Space: O(1)

int findLargest(node*root , int val) {
if (!root) //tree is empty
    printf("\ntree is empty") ; 
    exit(); 
if (val == root->value) {
    printf("\nOnly 1 element is present");
    exit();
}
node * element ;
if (val < root->value) 
    element = findElement(root->left , value);
else 
    element = findElement(root->right , value);

if (element->right == NULL)  {
    if (element = element->parent->left) { // the element is a left child . So its parent is the                         //next largest 
        return parent;
    }
    //Now the element is a right child . 
     if(element->value > root->value) { //the right most child of the right subtree from the //root node is the largest element
         printf("\nThis element is the largest in the tree");
         exit();
     } 
         
     while()  { // Now have to traverse back through the parent of  
    //each node till we reach the parent of the subtree which is a left child. Now the parent      //of this node will be the next largest.
          if (element = node->parent->left) {
              return parent->value;
          }
          element = element -> parent;
    }
  
}           

//Now the right child is not empty . So the next higher element will be the left-most child of the right-child .
element = element->right;
while(element->left != NULL) {
    element = element->left;
}
return element->value;
}   

findElement(node * root , int val) // This will do a tree traversal to find the right element.