BFS Acc Solution (Java and C# code)


  • 4

    Java:

    public int findSecondMinimumValue(TreeNode root) 
    {
        int rootVal = root.val;
        int secondSmall =Integer.MAX_VALUE;
        boolean diffFound = false;
        Queue<TreeNode> Q= new LinkedList<TreeNode>();
        Q.add(root);
    
        while(!Q.isEmpty())
        {
            TreeNode curr=Q.poll();
            if(curr.val!=rootVal && curr.val < secondSmall)
            {
                secondSmall=curr.val;
                diffFound=true;
            }
            if(curr.left!=null)
            {
                Q.add(curr.left);
                Q.add(curr.right);
            }
        }
    
        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;
        }
    

  • 0
    G

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


  • 0

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


  • 0
    V

    @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?


  • 0

    @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?


  • 0
    P

    @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;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            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();
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                    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;
        }
    
    

  • 0
    H

    @yashar said in BFS Acc Solution (Java and C# code):

    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


  • 0

    @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


  • 0
    C

    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.


  • 0
    P

    @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).


  • 0
    S

    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) {
            LinkedList<TreeNode> q = new LinkedList<TreeNode>();
            q.add(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);
                        if(tmp.left.val == root.val) q.add(tmp.left);
                        if(tmp.right.val == root.val ) q.add(tmp.right);
                    }
                }
            }
            return (min == Integer.MAX_VALUE) ? -1 : min;
    

  • 0
    H

    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.


  • 0
    L

    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;
        }
    }
    

Log in to reply
 

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