# Second Minimum Node In a Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/second-minimum-node-in-a-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## 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 1:**

![](https://assets.glich.co/dsa/second-minimum-node-in-a-binary-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/second-minimum-node-in-a-binary-tree/image1.jpg) 

**Input:** root = [2,2,2]
**Output:** -1
**Explanation:** The smallest value is 2, but there isn't any second smallest value.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 25]`.
* `1 <= Node.val <= 231 - 1`
* `root.val == min(root.left.val, root.right.val)` for each internal node of the tree.

# Approaches
## Brute Force: Traversal and Sorting
This approach involves traversing the entire binary tree to collect all unique node values. These unique values are then sorted to easily identify the second smallest value.
**Time:** O(N log N), where N is the number of nodes. The tree traversal takes O(N) time. Storing U unique values and then sorting them takes O(U log U), where U ≤ N. The sorting step dominates the complexity. · **Space:** O(N) in the worst case, to store all node values in the `HashSet` if they are all unique.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to be correct for any tree.
**Cons:** Suboptimal as it requires sorting, which is generally not necessary.; Fails to use the special property of the tree (`root.val = min(root.left.val, root.right.val)`) to improve efficiency.
### Explanation
This method treats the problem as a generic task of finding the second smallest element in a collection of numbers, ignoring the special structure of the tree. We first gather all unique values from the tree into a set to handle duplicates, then convert the set to a list and sort it. The second element of the sorted list is our answer.

```java
import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        Set<Integer> uniqueValues = new HashSet<>();
        dfs(root, uniqueValues);

        if (uniqueValues.size() < 2) {
            return -1;
        }

        List<Integer> sortedValues = new ArrayList<>(uniqueValues);
        Collections.sort(sortedValues);
        return sortedValues.get(1);
    }

    private void dfs(TreeNode node, Set<Integer> uniqueValues) {
        if (node == null) {
            return;
        }
        uniqueValues.add(node.val);
        dfs(node.left, uniqueValues);
        dfs(node.right, uniqueValues);
    }
}
```
### Algorithm
- Initialize a `HashSet` to store unique node values.
- Perform a depth-first search (DFS) or breadth-first search (BFS) to traverse the tree.
- For each node visited, add its value to the `HashSet`. This automatically handles duplicates.
- After the traversal, convert the `HashSet` into a `List`.
- Sort the list in ascending order.
- If the list contains fewer than two elements, it means there is no second minimum value, so return -1.
- Otherwise, the second element in the sorted list (at index 1) is the second minimum value.

## Single Pass Traversal
A more efficient approach is to traverse the tree just once. During the traversal, we can keep track of the two smallest distinct values encountered so far.
**Time:** O(N), where N is the number of nodes. We visit every node in the tree exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion stack in the DFS approach. In the worst case of a skewed tree, this can be O(N).
**Pros:** Improves upon the brute-force approach by eliminating the sorting step.; Achieves linear time complexity.
**Cons:** It always traverses the entire tree, which can be inefficient if the second minimum value is located near the root.
### Explanation
Instead of collecting all values, we can find the second minimum in a single pass. We know `root.val` is the first minimum. We traverse the tree and look for any value that is greater than `root.val` but smaller than the second minimum found so far. This avoids the overhead of storing all values and sorting.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    long min2 = Long.MAX_VALUE;
    int min1;

    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        min1 = root.val;
        dfs(root);
        return (min2 == Long.MAX_VALUE) ? -1 : (int) min2;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        if (min1 < node.val && node.val < min2) {
            min2 = node.val;
        }
        dfs(node.left);
        dfs(node.right);
    }
}
```
### Algorithm
- From the problem description, we know `root.val` is the absolute minimum value in the tree. Let's call this `min1`.
- Initialize a variable, `min2`, to store the second minimum value. Initialize it to a value larger than any possible node value, like `Long.MAX_VALUE`, to indicate it hasn't been found yet.
- Traverse the tree using DFS or BFS.
- For each node, compare its value (`val`) with `min1` and `min2`.
- If `min1 < val < min2`, we have found a new, smaller candidate for the second minimum. Update `min2 = val`.
- After the traversal is complete, if `min2` is still `Long.MAX_VALUE`, it means no value greater than `min1` was found. Return -1.
- Otherwise, cast `min2` to an `int` and return it.

## Optimized Traversal (BFS with Pruning)
This is the most efficient approach, as it fully leverages the special property of the tree: `node.val = min(node.left.val, node.right.val)`. This property allows us to prune entire subtrees from our search, leading to better average-case performance.
**Time:** O(N), where N is the number of nodes. In the worst case (e.g., a tree where all nodes have the same value), we must visit every node. However, for many trees, the pruning significantly reduces the number of visited nodes. · **Space:** O(W), where W is the maximum width of the tree, for the BFS queue. In the worst case of a complete binary tree, this is O(N).
**Pros:** The most efficient approach on average due to intelligent search space pruning.; Effectively utilizes the unique structure of the input tree.
**Cons:** The worst-case time and space complexity are asymptotically the same as the non-optimized single-pass traversal.
### Explanation
We can optimize the traversal by making an observation. The first minimum value is `root.val`. Any node with a value greater than `root.val` is a candidate for the second minimum. If we encounter such a node, say `node`, then `node.val` is a candidate. All of its descendants will have values greater than or equal to `node.val`, so we don't need to explore that subtree any further to find a *smaller* second minimum. We only need to continue searching down paths where nodes have a value equal to `root.val`.

```java
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        long ans = Long.MAX_VALUE;
        int min1 = root.val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            
            if (current.val > min1) {
                ans = Math.min(ans, current.val);
                // Pruning: No need to explore children
            } else if (current.val == min1) {
                if (current.left != null) {
                    queue.offer(current.left);
                    queue.offer(current.right);
                }
            }
        }
        
        return ans == Long.MAX_VALUE ? -1 : (int) ans;
    }
}
```
### Algorithm
- The minimum value in the tree is `min1 = root.val`. We are looking for the smallest value strictly greater than `min1`.
- Initialize a variable `ans` to `Long.MAX_VALUE` to track the second minimum found so far.
- Use a queue for a breadth-first search (BFS), starting with the `root`.
- While the queue is not empty, dequeue a node.
- If the node's value is greater than `min1`, it's a candidate for the second minimum. We update `ans = min(ans, node.val)`. We do not need to explore this branch further, so we don't add its children to the queue (pruning).
- If the node's value is equal to `min1`, the second minimum could be in its subtrees. We add its children to the queue to continue the search.
- After the traversal, if `ans` remains `Long.MAX_VALUE`, no second minimum was found. Return -1. Otherwise, return `(int) ans`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans = - 1 ; public int findSecondMinimumValue ( TreeNode root ) { dfs ( root , root . val ); return ans ; } private void dfs ( TreeNode root , int val ) { if ( root != null ) { dfs ( root . left , val ); dfs ( root . right , val ); if ( root . val > val ) { ans = ans == - 1 ? root . val : Math . min ( ans , root . val ); } } } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var findSecondMinimumValue =
  function (root) {
    let ans = -1;
    const v = root.val;
    function dfs(root) {
      if (!root) {
        return;
      }
      dfs(root.left);
      dfs(root.right);
      if (root.val > v) {
        if (ans == -1 || ans > root.val) {
          ans = root.val;
        }
      }
    }
    dfs(root);
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans = - 1 ; int findSecondMinimumValue ( TreeNode * root ) { dfs ( root , root -> val ); return ans ; } void dfs ( TreeNode * root , int val ) { if ( ! root ) return ; dfs ( root -> left , val ); dfs ( root -> right , val ); if ( root -> val > val ) ans = ans == - 1 ? root -> val : min ( ans , root -> val ); } };
```

### Python

```python
# 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 : def dfs ( root ): if root : dfs ( root . left ) dfs ( root . right ) nonlocal ans , v if root . val > v : ans = root . val if ans == - 1 else min ( ans , root . val ) ans , v = - 1 , root . val dfs ( root ) return ans
```