C++ Solution, Easy, Clean, Intuitive - O(n) time and O(1) space. beats 90% of submissions.

  • 0
    class Solution {
        TreeNode* findShortest(TreeNode *root)
            while (root->left)
                root = root->left;
            return root;
        bool find(TreeNode *root, TreeNode *p, TreeNode* &result)
            if (root)
                if (root == p)
                    return true;
                bool left = find(root->left, p, result);
                // the first left side ancestor will be the inorder ancestor
                if (left == true)
                    if (result == NULL)
                        result = root;
                    return true;
                return find(root->right, p, result);
            return false;
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if (p->right != NULL)
                return findShortest(p->right);
            TreeNode *result = NULL;
            find(root, p, result);
            return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.