#### Approach #1 Simple tree traversal [Accepted]

**Algorithm**

Based on the problem description, **the root node will always have the minimum value of the whole tree**. This property also holds tree for any subtree. Now we can turn the problem to be "find the minimum value in the tree that is greater than the root's value -- call it `min`

".

In any subtree, as long as the root's value is greater than the `min`

, then we don't need to look into that subtree anymore (because the **bold** property we have above). Otherwise, we need to look into the left and right subtree, and choose the minimum value that's greater than `min`

.

See more explanation in the comments below.

**Java**

```
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findSecondMinimumValue(TreeNode root) {
if (root == null) return -1;
int min = root.val;
int res = helper(root, min);
return res == Integer.MAX_VALUE ? -1 : res;
}
private int helper(TreeNode n, int min) {
if (n == null) return Integer.MAX_VALUE;
// If n.val > min, then just return,
// because n.val will be the mimimum value of the current subtree.
if (n.val > min) return n.val;
// If n.val is not > min, then n.val == min.
// Remember min is the global minimum.
if (n.left != null && n.right != null) {
return Math.min(helper(n.left, min), helper(n.right, min));
}
// Don't return -1 here.
return Integer.MAX_VALUE;
}
}
```

**Complexity Analysis**

- Time complexity : Averagely $$O(depth)$$, worst case $$O(n)$$.

Averagely, it will only need to traverse the depth of the tree to find the result. In worst case (where all the nodes have the same value as `min`

), it will need to visit every node to find the result.