# 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)`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kseb0.gitbook.io/whiteboard/second-minimum-node-in-a-binary-tree-671.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.