Inorder successor

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

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

Solution: Iterative

1. Start from the root
2. If target node is in the left subtree, set root as potential successor and move to left subtree.
3. If target node is in the right subtree, go to the right subtree. We don't need to update successor if target node lies in the right subtree.

Time Complexity - O(h)， Space Complexity - O(1)

    TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
        TreeNode *node = root, *successor = NULL;
        while (node) {
            if (p->val < node->val) {
                successor = node;
                node = node->left;
            } else {
                node = node->right;
            }
        }
        return successor;
    }

Solution: Recursive

上面那种方法也可以写成递归形式，写法也比较简洁，但是需要把思路理清，当根节点值小于等于p节点值，说明p的后继节点一定在右子树中，所以对右子节点递归调用此函数，如果根节点值大于p节点值，那么有可能根节点就是p的后继节点，或者左子树中的某个节点是p的后继节点，所以先对左子节点递归调用此函数，如果返回空，说明根节点是后继节点，返回即可，如果不为空，则将那个节点返回

TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
    if (!root) return NULL;
    if (p->val >= root->val) {
        return inorderSuccessor(root->right, p);
    } else {
        TreeNode *left = inorderSuccessor(root->left, p);
        return left ? left : root;
    }
}

Solution: Iterative Inorder Traversal

We can use iterative inorder traversal to find the successor. We just need to add a flag to indicate we have found the target node If we have already found the node, we just return the next node.

TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
    TreeNode *cur = root;
    stack<TreeNode*> s;
    bool found = false;

    while (cur || !s.empty()) {
        if(cur) {
            s.push(cur);
            cur = cur->left;
        } else {
            TreeNode* node = s.top();
            s.pop();

            if (found) return node;
            if (node == p) found = true;
            cur = node->right;
        }
    }
    return NULL;
}