Successor - Binary Search Tree

在 BST 當中， Successor(X) 代表 比 X 大的下一個數字。
通常可以用來找 Nth smallest  node.

找 X 的 Successor

1. 如果 X 有右子樹，則找出右子樹中最小值
2. 如果 X 沒有右子樹，則往 Parent 方向搜尋
3. 如果 X 是 X->Parent 的右子樹的話，則繼續往 X->Parent->Parent 找
   直到找到X->Parent 為 X->Parent->Parent 的左子樹

    // min of right subtree

    if(root->right != NULL) return min(root->right);

    // ancestor of node without right subtree

    BST* ancestor = root->parent;

    while(ancestor != NULL && ancestor->right == root)

    {

        root = ancestor;

        ancestor = ancestor->parent;

    }

    return ancestor->data;

}

參考： http://analgorithmaday.blogspot.tw/2011/03/successor-and-predecessorbst.html