# 671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly `two` or `zero` sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

``````Input:
2
/ \
2   5
/ \
5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
``````

Example 2:

``````Input:
2
/ \
2   2

Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
``````

``````class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
int first = root->val, second = INT_MAX;
helper(root, first, second);
return (second == first || second == INT_MAX) ? -1 : second;
}
void helper(TreeNode* node, int& first, int& second) {
if (!node) return;
if (node->val != first && node->val < second) {
second = node->val;
}
helper(node->left, first, second);
helper(node->right, first, second);
}
};
``````

``````class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
return helper(root, root->val);
}
int helper(TreeNode* node, int first) {
if (!node) return -1;
if (node->val != first) return node->val;
int left = helper(node->left, first), right = helper(node->right, first);
return (left == -1 || right == -1) ? max(left, right) : min(left, right);
}
};
``````

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

``````class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
int first = root->val, second = INT_MAX;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
auto t = q.front(); q.pop();
if (t->val != first && t->val < second) {
second = t->val;
}
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return (second == first || second == INT_MAX) ? -1 : second;
}
};
``````

Kth Smallest Element in a BST

https://discuss.leetcode.com/topic/102277/java-4-lines

https://discuss.leetcode.com/topic/102027/c-dfs-recursion

https://discuss.leetcode.com/topic/102035/bfs-acc-solution-java-and-c-code

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation