[4.5] Inorder Successor in Binary Search Tree

1. Example
http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/



In the above diagram,
Case1: Has right child, go anyway:  inorder successor of 8 is 10,
Case2: No right child and itself is left child :    inorder successor of 10 is 12 
Case3: No right child and itself is right child:   inorder successor of 14 is 20.
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html



2. Implementation

public static TreeNode inorderSuccessor(TreeNode e)
{
        


       // valdiate the input
       if ( e == null )
           return null;


   
 
       TreeNode succ;



       // Case 1: Has right child
       if ( e.parent == null || e.right != null )
       {
            succ = leftMostChild(e.right);
       }
       // Case 2,3: No right child
       else
       {
            // case 
            while(   (succ = e.parent) != null )
            {
                 // Case2: No right child and itself is left child
                 if ( succ.left == e)
                     break;
                 // Case3: No right child and itself is right child 
                 e = succ;
            }
       } 



       return succ;

  
}
public static TreeNode leftMostChild(TreeNode e)
{


      // vlaidate the input
      if ( e == null)
        return null;


      // while(e!= null) // NOTE: STOP at e == null, not we want
      while ( e.left!= null ) // NOTE: STOP at e.left == null 
         e = e.left;


      return e;

}

3. Similar Ones