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

• 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.

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