Solution


Approach #1: Brute Force [Accepted]

Intuition and Algorithm

Traverse the tree with a depth-first 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: Ad-Hoc [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 depth-first search may store up to information in the call stack, where is the height of the tree.


Analysis written by: @awice