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

# Second Minimum Node In a Binary Tree (671)

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

### Approach 1 : DFS

1. The KEY point of this problem is to observe that this tree's **root node's val is always the smallest value**.
2. We then use an Array with `index 0` being the value at the root.node and `index 1` being the location which will store the second smallest value. \*\*Additionnally, I used an `Integer` object for the array in lieu of a primitive (`int`) array to avert an error in the advent that the only other element in the tree is `Integer.MAX_VALUE`. (primitive long array type would have also worked as it can compare numbers that are greater than 31bit like the aforementioned).
3. Upon this fact, we ***traverse the tree's node recursively*** and ***while the node that we're currently visiting does not equal what was at the initial root node(res\[0]),** we* ***update res\[1] to take the smallest node's value*** that we visit ------- Since the array is passed by reference, we always have have access to res\[0] which is subsequently used as an anchor to compare each nodes and make sure they do not equal to the initial root.val.

\*\*(primitive long array type would have also worked to compare `Integer.MAX_VALUE` has it can store more than 31bits.

`Time: O(N)        Space: O(1)`

```java

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        Integer[]res = {root.val, null};
        
        findMin(root, res);
        
        return res[1] == null ? -1 : res[1];
    }
    private void findMin(TreeNode root, Integer[]res){
        if(root == null) return;
        
        findMin(root.left, res);
        findMin(root.right, res);
        
        if(root.val != res[0]){
            res[1] = res[1] == null ? root.val : Math.min(res[1], root.val);
        }
    }
}
```

### **Approach 2 : BFS**

I used a level order traversal and implemented the same logic above. (see 1.3)

```java
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Integer secondMin = null;
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.val != root.val){
                secondMin = secondMin == null ? node.val : Math.min(secondMin, node.val);
            }
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        return secondMin == null ? -1 : secondMin;
    }
}
```

`Time: O(N)        Space: O(N)`