# LeetCode: 671. Second Minimum Node In a Binary Tree

**The Problem**

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. More formally, the property `root.val = min(root.left.val, root.right.val)`

always holds.

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

```
Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
```

**Solution**

**Solution**

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

```
int findSecondMinimumValue(TreeNode* root) {
map<unsigned, unsigned> ordered;
findSecondMinimumValue(root, ordered);
if (ordered.size() < 2) return -1;
auto it = ordered.begin();
++it;
return it->first;
}
void findSecondMinimumValue(TreeNode* root, map<unsigned, unsigned> &ordered) {
if (root == nullptr) return;
ordered[root->val] = 1;
findSecondMinimumValue(root->left, ordered);
findSecondMinimumValue(root->right, ordered);
}
```

Let's break it down step by step:

- The function
`findSecondMinimumValue`

takes a pointer to the root node of a binary tree as its parameter and returns an integer value. - Inside the
`findSecondMinimumValue`

function, a`map<unsigned, unsigned>`

named`ordered`

is declared. A`map`

is a data structure that stores key-value pairs in a sorted order based on the keys. In this case, the map is being used to keep track of the existence of each value encountered in the tree. - The main function,
`findSecondMinimumValue`

, is then called with the root of the binary tree and the`ordered`

map. This function is responsible for populating the`ordered`

map with the values from the binary tree. - The function first checks if the provided
`root`

pointer is`nullptr`

, which would indicate an empty subtree. If it's empty, the function simply returns, as there's nothing to process. - If the
`root`

is not`nullptr`

, the code proceeds to add the value of the current node (`root->val`

) to the`ordered`

map. This step helps keep track of the existence of the values in the tree. - The function then recursively calls itself on the left and right children of the current node (
`root->left`

and`root->right`

). This recursive process continues until all nodes in the binary tree have been visited. - After the
`findSecondMinimumValue`

function has processed the entire tree and populated the`ordered`

map with value existences, the main function proceeds. - The main function first checks if the size of the
`ordered`

map is less than 2. If this is the case, it means there are not enough distinct values in the tree to find a second smallest value. In such a scenario, the function returns -1 to indicate that no second smallest value exists. - If the
`ordered`

map has at least 2 distinct values, it means there's a possibility of finding a second smallest value. The code obtains an iterator (`it`

) pointing to the beginning of the`ordered`

map and then increments the iterator once using`++it`

. This is done to move the iterator to the second smallest value in the map. - Finally, the function returns the key of the element pointed to by the iterator
`it`

, which represents the second smallest value in the binary tree.