2 approaches to this problem


  • 0
    T

    I figured out the naive approach first.....

    time complexity : O(n) n is the size of the tree nodes
    space complexity: O(n)

    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            
            //special case
            if(root == nullptr || (root->left == nullptr && root->right == nullptr))
            {
                return nullptr;
            }
            
            vector<TreeNode*> res;
            stack<TreeNode*> stk;
            while(!stk.empty() || root != nullptr)
            {
                if(root != nullptr)
                {
                    stk.push(root);
                    root = root->left;
                }
                else
                {
                    root = stk.top();
                    stk.pop();
                    if(!res.empty() && p == res.back())
                    {
                        return root;
                    }
                    res.push_back(root);
                    root = root->right;
                }
            }
            return nullptr;
        }
    };
    

    And The code below is a more efficient algorithm with explanation

    time complexity : O(log(n)) n is the size of the tree nodes
    space complexity: O(1)

    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            
            if(root == nullptr)
            {
                return nullptr;
            }
            
            // if the p's value is greater than root's, run the recursive function directly.
            //because root could not be the successor of p
            if(root->val <= p->val)
            {
                return inorderSuccessor(root->right, p);
            }
            //if the p's value is less than root's, run the recursive function first
            //Then compare the values between leftCandidate and root, choose the smaller one.
            TreeNode* leftCandidate = inorderSuccessor(root->left, p);
            return leftCandidate != nullptr && leftCandidate->val < root->val ? leftCandidate : root;
        }
    };

  • 0
    H

    I think check "leftCandidate->val < root->val" is not necessary.

    In my understanding, we are actually looking for the first node that its value is larger than p.val.
    So, in case "root->val <= p->val", we will just return the result, but in case "root->val > p->val", we will assign the return value to be the first node that its value is larger than p.val. In later backtrack, if we found the return value has been assigned to a non-null value, we will keep return it even its value is larger than p.val.

    Correct me if I am wrong


Log in to reply
 

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