Question: Find the next in order node of given node in binary tree. Write the program of same. pointer to parent node is given.

Solution: static Node nextNode(Node head){
Node returnNode;
if (head.rightChild != null){
//If we have a right child, the next obvious in order
//node would be the desendent of the right child.
returnNode = head.rightChild;
while(returnNode.leftChild != null)
returnNode = returnNode.leftChild;
}else{
//Else climb up the tree till we get the ancestor that
// that is supposed to be the next node
Node tempPointer = head;
Node curPointer = head;
while(curPointer != null && curPointer.leftChild != tempPointer){
tempPointer = curPointer;
curPointer = curPointer.parent;
}
returnNode = curPointer;
}
return returnNode;
}