Inorder Successor in BST

LeetCode #285

Description:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Example:

Note

Idea:

1. 如果right subtree not null, 找它的min value
2. 否则，从root开始找。往左的时候现在有可能是successor，往右的时候不可能。

Time: O(h)

Code:

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(p->right != NULL){
            return minValue(p->right);
        }

        TreeNode * succ=NULL;
        while(root->val != p->val){
            if(p->val < root->val){
                succ=root;
                root=root->left;
            }
            else if(p->val > root->val){
                root=root->right;
            }
        }

        return succ;
    }

    TreeNode * minValue(TreeNode * root){
        while(root->left !=NULL){
            root=root->left;
        }
        return root;
    }
};