Solution
Approach #1: Brute Force [Accepted]
Intuition and Algorithm
Traverse the tree with a depthfirst search, and record every unique value in the tree using a Set structure uniques
.
Then, we'll look through the recorded values for the second minimum. The first minimum must be .
Complexity Analysis

Time Complexity: , where is the total number of nodes in the given tree. We visit each node exactly once, and scan through the values in
unique
once. 
Space Complexity: , the information stored in
uniques
.
Approach #2: AdHoc [Accepted]
Intuition and Algorithm
Let . When traversing the tree at some node, , if , we know all values in the subtree at are at least , so there cannot be a better candidate for the second minimum in this subtree. Thus, we do not need to search this subtree.
Also, as we only care about the second minimum , we do not need to record any values that are larger than our current candidate for the second minimum, so unlike Approach #1 we can skip maintaining a Set of values(uniques
) entirely.
Complexity Analysis

Time Complexity: , where is the total number of nodes in the given tree. We visit each node at most once.

Space Complexity: . The information stored in and is , but our depthfirst search may store up to information in the call stack, where is the height of the tree.
Analysis written by: @awice