> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/tree/671-second-minimum-node-in-a-binary-tree.md).

# 671 Second Minimum Node In a Binary Tree

## 671. Second Minimum Node In a Binary Tree

## 1. Question

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

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }

        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        Queue<TreeNode> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }

                if (set.contains(curNode.val)) {
                    continue;
                }

                set.add(curNode.val);

                if (curNode.val < min) {
                    secondMin = min;
                    min = curNode.val;
                }
                else if (curNode.val < secondMin) {
                    secondMin = curNode.val;
                }
            }
        }
        return set.size() < 2 ? -1 : secondMin;
    }
}
```

**(2) DFS**

```java
/**
 * 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) {
        int[] res = new int[2];
        Arrays.fill(res, Integer.MAX_VALUE);
        Set<Integer> set = new HashSet();
        dfs(root, set, res);
        return set.size() < 2 ? -1 : res[0];
    }
    
    public void dfs(TreeNode node, Set<Integer> set, int[] res) {
        if (node == null) return;
        
        if (!set.contains(node.val)) {
            set.add(node.val);
            if (node.val < res[1]) {
                res[0] = res[1];
                res[1] = node.val;
            }
            else if (node.val < res[0]) {
                res[0] = node.val;
            }
        }
        
        dfs(node.left, set, res);
        dfs(node.right, set, res);
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度O(n), 空间复杂度O(w)

DFS: 时间复杂度O(n)， 空间复杂度O(h)