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.
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:
Input:
2
/ \
2 5
/ \
5 7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:
2
/ \
2 2
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
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.
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