Inorder Predecessor in BST

Description:

Example:

Note

Idea:

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

Time: O(h)

Code:

class Solution {
public:
    TreeNode* inorderPredecessor(TreeNode* root, TreeNode* p) {
        if(p->left != NULL){
            return maxValue(p->left);
        }

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

        return predec;
    }

    TreeNode * maxValue(TreeNode * root){
        while(root->right !=NULL){
            root=root->right;
        }
        return root;
    }
};