package leetCode.week2;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_671_13 {

    /**
     * 
     * BFS
     * 
     * 
     * 
     * 
     *
     * 
     *
     * BFS
     * O(N)
     *
     * @param root 
     * @return 
     */
    public int findSecondMinimumValue(TreeNode root) {
        Queue queue = new LinkedList();

        queue.add(root);

        int firstMin = root.val;
        int secondMin = Integer.MAX_VALUE;
        TreeNode node;
        boolean isChange = false;

        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node.val < firstMin) {
                secondMin = firstMin;
                firstMin = node.val;
                isChange = true;
            } else if (node.val == firstMin || node.val > secondMin) {
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                continue;
            } else if (node.val > firstMin){
                secondMin = node.val;
                isChange = true;
            }
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        if (!isChange) secondMin = -1;

        return secondMin;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}