BFS Acc Solution (Java and C# code)

• Java:

``````public int findSecondMinimumValue(TreeNode root)
{
int rootVal = root.val;
int secondSmall =Integer.MAX_VALUE;
boolean diffFound = false;

while(!Q.isEmpty())
{
TreeNode curr=Q.poll();
if(curr.val!=rootVal && curr.val < secondSmall)
{
secondSmall=curr.val;
diffFound=true;
}
if(curr.left!=null)
{
}
}

return (secondSmall == Integer.MAX_VALUE && !diffFound) ? -1 : secondSmall;
}
``````

C#:

``````    public int FindSecondMinimumValue(TreeNode root)
{
int rootVal = root.val;
int secondSmall = int.MaxValue;
bool diffFound = false;
Queue<TreeNode> Q = new Queue<TreeNode>();
Q.Enqueue(root);

while (Q.Any()) //while Q is not empty
{
TreeNode curr = Q.Dequeue();
if (curr.val != rootVal && curr.val <= secondSmall)
{
secondSmall = curr.val;
diffFound = true;
}
if (curr.left != null)
{
Q.Enqueue(curr.left);
Q.Enqueue(curr.right);
}
}
return (secondSmall == int.MaxValue && !diffFound) ? -1 : secondSmall;
}
``````

• What if the number to return equals to int.maxValue?

• @Geekestcoder That will never happen! If root is `int.Maxvalue`, second smaller is definitely smaller than root. If not, return -1.

• @yashar
No. A node will never be smaller than its parent.

What if the root is `MAX_INT - 1`, and there is really a node with value `MAX_INT`?

• @vonzcy Exactly as you are saying, each node is not gonna be smaller than it's parent. So parent is smaller than its children. Same rule applies to root. So root of the given tree is the smallest node in the tree.
If the root value is `MAX_INT - 1`, its children are gonna be equal to it, or bigger.
If root value is `Max_INT` and all the sub trees and children are `MAX_INT` too, we will return -1, because this statement is never true `if (curr.val != rootVal && curr.val < secondSmall)` so we never update secondSmall.
Am I right?

• @vonzcy, good point, This program will fail on the test case [2147483646,2147483647], you can use a boolean flag to indicate whether all nodes in the tree have the same value, like this:

``````    public int findSecondMinimumValue(TreeNode root) {
if(root == null) return -1;
int min = root.val;
int secondMin = Integer.MAX_VALUE;
boolean allsame = true;
while(!queue.isEmpty()){
int size = queue.size();
int levelmin = Integer.MAX_VALUE;
for(int i = 0; i< size; i++){
TreeNode node = queue.poll();
levelmin = Math.min(levelmin, node.val);
if(node.val != min){
secondMin = Math.min(secondMin, node.val);
allsame = false;
}
}
if(levelmin > min) return secondMin;
}
if(allsame) return -1;
return secondMin;
}

``````

• If the root value is MAX_INT - 1, its children are gonna be equal to it, or bigger.

Right, so the output should be MAX_INT, not -1

• @Geekestcoder @vonzcy @panzw @hpplayer Thanks guys for the comments and feedback. I fixed the issue by adding a flag to check whether we find a different node during our traversal. `boolean diffFound`

• How is the condition given "If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes." used in the solution? I thought bfs solution is simply looking for 2nd min of all numbers.

• @chu4 the condition can be used for pre-termination. In BFS, we use `levelmin` to record the min value of each level, when `levelmin > min`. we don't need to search further because all nodes below will be `>= levelmin`. we just need to return secondmin we have seen so far.
This is a little trivial, because the worst case time complexity is still `O(N)`.

• Similar solution. But, a TreeNode is added to the queue only if it's value is equal to root.val.

``````public int findSecondMinimumValue(TreeNode root) {
int min = Integer.MAX_VALUE;
while(!q.isEmpty()) {
int n = q.size();
for(int i = 0; i < n; i++) {
TreeNode tmp = q.pop();
int tmpMin = Integer.MAX_VALUE;
if(tmp.left != null) {
if(tmp.left.val != root.val || tmp.right.val != root.val) {
if(tmp.left.val != root.val && tmp.right.val != root.val) {
tmpMin = Math.min(tmp.left.val, tmp.right.val);
}
else if(tmp.left.val != root.val) {
tmpMin = tmp.left.val;
}
else if(tmp.right.val != root.val) {
tmpMin = tmp.right.val;
}
}
min = Math.min(tmpMin, min);
}
}
}
return (min == Integer.MAX_VALUE) ? -1 : min;
``````

• The idea is very good. Just traverse all nodes and find the secondMin. But, your efficiency is not very high, because you don't make advantage of the feature of the tree. Each root is no smaller than it's children. So in every case, the time complexity is O(N), where N is the number of nodes. But, when using DFS, we can cut half of the tree, when the value of two sub trees' root' values are not identical. So, the time complexity of DFS is O(N) only in worst case, on average, it's O(log(n)). Hope it helps.

• Same idea ,I also use "BFS" to solve the problem but my solution cannot be accepted,I just use more than one integer to store the second minimum value . Could anyone can tell what's wrong with my code,please.
here is my code.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findSecondMinimumValue(TreeNode root) {
Stack<TreeNode> S=new Stack<>();
int min_first=Integer.MAX_VALUE;
int min_second=Integer.MAX_VALUE;
S.push(root);
while(!S.isEmpty())
{
TreeNode now=S.pop();
if(now.val<min_first)
{
min_second=min_first;
min_first=now.val;
}
if(now.val<min_second)
min_second=now.val;
if(root.left!=null) S.push(root.left);
if(root.right!=null) S.push(root.right);
}

if(min_second==min_first)
return -1;
return min_second;
}
}
``````

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