CareerCup

if largest element has no child then its parent.
if largest element has left child then left child.

I think we can do it by reverse inorder traversal

/* Function for reverse inorder */
int data;
void revInorder(struct node* root, int kthLargest)
{
     static int count = 0;
     if(root == NULL)
     {
             return;
     }
     revInorder(root->right, kthLargest);
     count++;
     if(count == kthLargest)
     {
         data = root->data;
         return;
     }
     revInorder(root->left, kthLargest);
}

scenarios: the max value has a left node and no right node, is leaf node.
if lead node - second largest element is its parent
if has left node, second largest element is its left child.
Runtime 0(logn)

There is a generalized version solution which find the k-largest elements in a BST at the entry "Find the k largest elements in a BST" code.google.com/p/elements-of-programming-interviews/wiki/Programs.

It seems that are solutions for another programming interviews book.

the parent of the largest node(right-most node).

public static final Node secondLargest(Node root) {
  if(root == null || root.next == null) {
    return null;
  }
  Node next = root.next;
  Node larger = next.next;

  if( larger != null) {
    return secondLargest(next);
  } else {
    return next;
  }
}

public static final Node secondLargest(Node root) {
  if(root == null || root.right == null) {
    return null;
  }
  Node next = root.right;
  Node larger = next.right;
  if( larger != null) {
    return secondLargest(next);
  } else {
    return root;
  }
}

Idea:
1. Find the right most node. If the right most node has no left child, then its parent is second largest.
2. If the right most node has a left child, then the largest in left part will be the second largest.
public static Node SecondLargest(Node root)
{
   if(root==null)||(root.left==null&&root.right==null)
       return null;
   Node large=root,secLarge;
   while(large.right!=null)
   {
        large=large.right;
        secLarge=large;
    }
    if(large.left==null)
       return secLarge;
   return Largest(large);
}

public static Node Largest(Node root)
{
    while(root.right!=null)
        root=root.right;
    return root;
}

1. Go to the right most node (will give you the largest node)
2. Get the predecessor of the above
a. If the largest node has a left subtree, get the max of that sub tree
b. Else, the parent of the largest node is the 2nd largest node.

You will probably get bonus points if you talk about implementing it in using max, predecessor.

go in-order and track the previous and current elements until end, sample of the code in Javascript:

var prev=null, current = null;

tree.inOrderTraversal(function(node){
  if(!prev){
    prev = current =  node;
  }
  else{
    prev = current;
    current = node;
  }
});

console.log(prev.data);

1. Go to the right most node
2.1 if it has left child , then the biggest value from its left child is the result
2.2 if not then the result is its parent.

Important : verify if the tree has at least 2 values

Why don't we try inorder traversal as it clearly mentioned its a BST. So, it will print elements in ascending order. So, the 2nd element from the right most is the answer.

private static Node secondLargest(Node root) {
        if (root == null || root.left == null && root.right == null) return null;
        Node curr=null,prev=null;
        if (root.right == null) {
                 curr= root.left;
            while (curr.right != null)
                curr = curr.right;
            return curr;

        }else{
            curr=root;
          while(curr.right!=null){
              prev=curr;
              curr=curr.right;
          }
              return prev;
        }
    }

//Using recursion .

void nthLargest(Node *root,int n)
{
if(root!=NULL)
{
nthLargest(root->right,n);
count++;
if(count==n)
printf("\n nthlarget element is %d",root->data);
}
}