Inorder Successor in BST

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

http://www.lintcode.com/en/problem/inorder-successor-in-binary-search-tree/

Discussion

It would be easy if it accepts O(n) runtime. Do inorder traversal, the successeor of a given node is the next node in the result array of inorder traversal.
The challenge is O(h) runtime. So everytime do make a selection, half of the nodes should be excluded. Two cases:

1. If the right child of the given node is NOT null, the most left node on the right subtree is its inorder successor (minimum of right substree).
2. If the right child of the given node is NULL, its successor is one of its ancestors. This ancestor has the smallest values among the ancestors whose value is larger than the given node. 也就是说我们要找到从最近的那个ancestor开始，在它的左子树上找到了要找的node。这个问题就成了用二分查找BST上的一个节点，并且记录下该节点之前最后一个比它大的node就是它的inorder successor。

Solution

O(n) runtime solution.

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // write your code here
        if(root==NULL) return NULL;
        vector<TreeNode*> nodes = inorderTraversal(root);
        for(int i=0; i<nodes.size()-1; i++) {
            if(nodes[i]->val == p->val) return nodes[i+1];
        }
        return NULL;
    }
private:
    vector<TreeNode*> inorderTraversal(TreeNode* root) {
        vector<TreeNode*> result;
        if(root == NULL) return result;
        TreeNode *curNode = root;
        stack<TreeNode*> mystk;
        while(curNode) {
            mystk.push(curNode);
            curNode = curNode->left;
        }
        while(mystk.empty() == false) {
            curNode = mystk.top();
            mystk.pop();
            result.push_back(curNode);
            curNode = curNode->right;
            while(curNode) {
                mystk.push(curNode);
                curNode = curNode->left;
            }
        }
        return result;
    }
};

O(h) solution.

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // write your code here
        if(root==NULL || p==NULL) return NULL;
        TreeNode *result=NULL;
        TreeNode *cur;
        if(p->right != NULL) {//CASE 1
            cur = p->right;
            while(cur->left != NULL) {
                cur = cur->left;
            }
            return cur;
        }
        cur = root;
        while(cur != NULL) {//CASE 2
            if(p->val < cur->val) {
                result = cur;
                cur = cur->left;
            } else if(p->val > cur->val) {
                cur = cur->right;
            } else
                break;
        }
        return result;
    }
};

Follow up

What if to find the predecessor in BST? 跟找successor相反:

1. 如果左子树不为空，找左子树上最右的节点。
2. 如果左子树为空，从root开始二分查找，记录下最近一个比p小的节点。