C++ Solution 3ms constant space (intuition + explanation)


  • 0

    Intuition
    This tree is actually a heap, where the parent will always be less than or equal to its children. (An even stricter constraint is that one of its children must be equal to the parent.)

    Edge Cases
    If all the nodes have the same value, there is no second min.

    Algorithm

        int findSecondMinimumValue(TreeNode* root) {
            if (!root || (!root->left && !root->right)) return -1;
            int left = root->left->val > root->right->val ? root->left->val : findSecondMinimumValue(root->left);
            int right = root->right->val > root->left->val ? root->right->val : findSecondMinimumValue(root->right);
            if (left == -1) return right;
            if (right == -1) return left;
            return min(left, right);
        }
    

    Explanation
    When the children are not equal, the greater one is a potential candidate for the second min. However, we must still recurse on the child with the lesser value, because we might find a second min smaller than the candidate of the current context on the side of the smaller child. Here is an "uncompressed" version, if you will, of the above solution, that makes it more clear what the possible cases are:

        int findSecondMinimumValue(TreeNode* root) {
            if (!root || (!root->left && !root->right)) return -1;
            int left;
            int right;
            if (root->right->val == root->left->val) {
                left = findSecondMinimumValue(root->left);
                right = findSecondMinimumValue(root->right);
                if (left == -1) return right;
                if (right == -1) return left;
                return min(left, right);    
            }
            if (root->right->val > root->left->val) {
                right = root->right->val; // candidate 2nd min
                left = findSecondMinimumValue(root->left);
                if (left == -1) return right;
                return min(left, right);
            }
            if (root->left->val > root->right->val) {
                left = root->left->val; // candidate 2nd min
                right = findSecondMinimumValue(root->right);
                if (right == -1) return left;
                return min(left, right);
            }   
        }
    

    Complexity Analysis
    In the worst case, each node is hit once. So the algorithm runs in O(n), for n nodes in the tree.


Log in to reply
 

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