# LeetCode 671: Second Minimum Node In a Binary Tree

## Problem Restatement

We are given a non-empty special binary tree.

The tree has these rules:

| Rule | Meaning |
|---|---|
| Children count | Each node has either `0` or `2` children |
| Parent value | If a node has children, its value is the smaller value among its two children |
| Goal | Find the second minimum value in the whole tree |

If no second minimum value exists, return `-1`.

Because each parent stores the smaller value of its children, the root always contains the minimum value in the entire tree. The task is to find the smallest value strictly greater than the root value.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Root of a special binary tree |
| Output | The second minimum value, or `-1` |
| Minimum value | Always stored at the root |
| Second minimum | Smallest value strictly greater than `root.val` |

Example function shape:

```python
def findSecondMinimumValue(root: Optional[TreeNode]) -> int:
    ...
```

## Examples

Consider this tree:

```text
    2
   / \
  2   5
     / \
    5   7
```

The values in the tree are:

```text
2, 2, 5, 5, 7
```

The minimum value is:

```text
2
```

The second minimum value is:

```text
5
```

So the answer is:

```python
5
```

Now consider:

```text
  2
 / \
2   2
```

All values are the same.

There is no value strictly greater than `2`.

So the answer is:

```python
-1
```

## First Thought: Collect All Values

A direct solution is to traverse the tree, collect all node values into a list, remove duplicates, sort the values, and return the second value.

This works, but it stores more data than needed.

We already know the smallest value:

```python
root.val
```

So we only need to find the smallest value greater than `root.val`.

## Key Insight

Because of the special tree property, the root value is the global minimum.

Therefore, every node value is either:

1. Equal to `root.val`
2. Greater than `root.val`

The answer is the smallest value in the second group.

So we can run DFS and keep one variable:

```python
answer
```

Whenever we find a node value greater than the root value, it becomes a candidate for the second minimum.

We keep the smallest candidate.

## Pruning Observation

There is also a useful pruning rule.

If a node value is already greater than the root value, then this node is a candidate.

Because every descendant of that node must be greater than or equal to that node, no descendant can give a smaller candidate.

So once we see:

```python
node.val > root.val
```

we can return `node.val` for that subtree.

This gives a clean recursive solution.

## Algorithm

Use a helper function:

```python
dfs(node)
```

It returns the second minimum candidate inside that subtree, or `-1` if none exists.

For each node:

1. If `node` is `None`, return `-1`.
2. If `node.val > minimum`, return `node.val`.
3. Recursively search the left subtree.
4. Recursively search the right subtree.
5. If both sides return valid candidates, return the smaller one.
6. If only one side is valid, return that one.
7. If neither side is valid, return `-1`.

## Correctness

The root value is the minimum value of the whole tree because each internal node stores the smaller value of its children.

The DFS helper searches for the smallest value strictly greater than this minimum.

If a node value is greater than the minimum, that node is a valid second-minimum candidate. Its descendants cannot contain a smaller candidate, because the special tree property implies descendants are greater than or equal to their ancestors. Therefore, returning that node value for the subtree is correct.

If a node value equals the minimum, the second minimum may still appear in either child subtree, so the algorithm searches both children.

For each subtree, the helper returns the smallest valid candidate in that subtree, or `-1` if none exists. Combining the left and right results by taking the smaller valid candidate gives the smallest valid candidate for the current subtree.

Applying this logic at the root returns the smallest value strictly greater than the global minimum. If no such value exists, the algorithm returns `-1`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | In the worst case, every node is visited |
| Space | `O(h)` | Recursion stack depends on tree height |

Here, `n` is the number of nodes and `h` is the height of the tree.

## Implementation

```python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        minimum = root.val

        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return -1

            if node.val > minimum:
                return node.val

            left = dfs(node.left)
            right = dfs(node.right)

            if left == -1:
                return right

            if right == -1:
                return left

            return min(left, right)

        return dfs(root)
```

## Code Explanation

The root value is the global minimum:

```python
minimum = root.val
```

The helper returns the second-minimum candidate inside a subtree:

```python
def dfs(node: Optional[TreeNode]) -> int:
```

If the node is missing, it gives no candidate:

```python
if node is None:
    return -1
```

If the node value is greater than the root value, it is a candidate:

```python
if node.val > minimum:
    return node.val
```

We can return immediately because descendants cannot improve this candidate within that subtree.

If the node value equals the minimum, the answer may be deeper:

```python
left = dfs(node.left)
right = dfs(node.right)
```

If one side has no candidate, return the other side:

```python
if left == -1:
    return right

if right == -1:
    return left
```

If both sides have candidates, return the smaller one:

```python
return min(left, right)
```

## Testing

```python
def run_tests():
    s = Solution()

    # Tree:
    #     2
    #    / \
    #   2   5
    #      / \
    #     5   7
    root = TreeNode(2)
    root.left = TreeNode(2)
    root.right = TreeNode(5, TreeNode(5), TreeNode(7))

    assert s.findSecondMinimumValue(root) == 5

    # Tree:
    #   2
    #  / \
    # 2   2
    root = TreeNode(2, TreeNode(2), TreeNode(2))

    assert s.findSecondMinimumValue(root) == -1

    # Single node.
    root = TreeNode(1)

    assert s.findSecondMinimumValue(root) == -1

    # Candidate appears in the left subtree.
    root = TreeNode(1)
    root.left = TreeNode(1, TreeNode(1), TreeNode(3))
    root.right = TreeNode(1, TreeNode(1), TreeNode(5))

    assert s.findSecondMinimumValue(root) == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard sample | Finds second minimum `5` |
| All values equal | Returns `-1` |
| Single node | No second value exists |
| Candidate in deeper subtree | Confirms recursive search |