CareerCup

This problem can be solved by modified inorder traversal.
conventional inorder-
---------------------
visit left child
root
then right child
---------------------
modified inorder-
------------------------
1>first visit right child
2> then root
3>then left child
-------------------------
In b/w them we can keep track of last visited node.(Let prev)
when we shall find the actual node we would have next biggest node(in prev).
O(n)

You can simply find the successor of the given Node.
Takes O(logN) time, if you do inorder traversal it will take O(N) time.

if(Node->right!=NULL)
{
     Node=Node->right;
     while(Node->left!=NULL)
          Node=Node->left;
} 
else
{
    while(Node->parent!=NULL || Node==Node->parent->right)
                Node=Node->parent;
}
return Node;

// To get maximum value in the tree.
public int getMax(BinarySearchTree rootNode) {
BinarySearchTree rNode = rootNode;
int res = 0;
while (true) {
if (rNode.rightNode != null) {
rNode = rNode.rightNode;
} else {
if (rNode != null) {
res = rNode.value;
}
break;
}
}
return res;
}

Inorder traversal with memory; basically return the node traversed immediately after we find our target. This assumes we have the root to start, which is not mentioned in the problem, but you need it to find a solution.

Node* next_biggest(Node* curr, Node* n, bool& return_next) {
  if (!curr) return NULL;
  // Recursively call left subtree
  Node* ret;
  if (ret = next_biggest(curr->left, n, return_next)) return ret;
  // These two statements will be executed
  // on each node in smallest to biggest order
  if (return_next) return curr;
  if (curr == n) return_next = true;
  // Recursively call right subtree
  if (ret = next_biggest(curr->right, n, return_next)) return ret;
  return NULL;
}

Is the answer only possible to be one of the three nodes: the direct parent, the very right node of its left subtree and the very left node of its right subtree?

struct node * search(struct node *root, struct node *elem)
{

if(!root || !elem) return;

if(elem->right != NULL) {

elem = elem->right;
while(elem->left) {
elem = elem->left;
}
return elem;
}
struct node *result = NULL;

while(root) {

if(elem->data < root->data) {
result = root;
root = root->left;
}
else if (elem->data > root->data)
root = root->right;
else
break;


}
return result;
}

Perhaps I don't understand what "biggest" means but in a BST (Binary Search Tree) nodes with larger values are on the right, and nodes with smaller values are on the left, or else it is not a binary search tree. Sounds like a trick question to me

// find the next biggest node in BST
Node* FindNextBiggest(Node* r, Node* cur)
{
    if(r == null || cur == null)
		return null;

    // if cur is the root, return the min on the right child.
	if (cur->value == r->value)
	{
	    return FindMin(r->right);
	}
	else if(cur->value < r->value)
	{
	    // if cur is on the left child, try to get the next biggest on the left child.
	    // if left child does not have the next biggest, return root.
	    Node *bigger = FindNextBiggest(r->left, cur);
		return bigger == null ? r : bigger;
	}
	else
	{
	    // if cur is on the right child, get the next biggest on the right child.
	    // return null if cur points to the maximum in the tree.
		return FindNextBiggest(r->right, cur));
	}
}

Node* FindMin (Node* r)
{
	if(r == null)
		return null;

    Node* p = r;
	while(p->left != null)
		p = p->left;

	return p;
}

class Node {
	int value;
	Node parent;
	Node left;
	Node right;
}

Node  findNextSmallest(Node n) {
	return Min(findMin(n.right), n.parent.value, findMin(n.parent.right) );
}

findMin(Node n) {
	if (n == Null)
		return Integer.MAX_INT;
	else 
		return Math.min(n.value, findMin(n.left));
}