Inorder successor ?

This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ?

Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree. Otherwise, find the first ancestor that has node U in the left sub-tree.

Pseudocode :

if(node->right)
if( ! node->right->left)
return node->right;
else
{
tmp = node->right->left;
while(tmp->left)
tmp = tmp->left;
return tmp;
}