Write a function to find the 2nd largest element in a binary search tree

This should be the predecessor of the largest item. In a binary search tree, the largest item is the rightmost  node.

Int GetMax(Node root)

{

  if (root == null) return root;

  while (root.right != null)

         root = root.right;

  return root;

}

Node GetPredecessor(Node root)

{

if (root == null) return null;

if (root.left)

{

Node current = root.left;

while(current && current.right)

   current = current.right;

return current;

}

Node parent = root.parent;

while(parent && parent.left == root)

{

   root = parent;

   parent =parent.parent;

}

return parent;

}

Find the duplicate element in an array of n+1 integers in the range 1 to n.


One of the common approaches is to sort the numbers then use binary chop
Or use the property that the sun of consecutive n numbers is n (n+1)/2