This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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 7Output:5Explanation:The smallest value is 2, the second smallest value is 5.

**Example 2:**

Input:2 / \ 2 2Output:-1Explanation:The smallest value is 2, but there isn't any second smallest value.

b'

\n\n## Solution

\n

\n#### Approach #1: Brute Force [Accepted]

\n

\n#### Approach #2: Ad-Hoc [Accepted]

\n

\n

'
\n

**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 .

\n\n**Complexity Analysis**

- \n
- \n
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

\n`unique`

once. \n - \n
Space Complexity: , the information stored in

\n`uniques`

. \n

\n

**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.

\nAlso, 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**

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

\n \n - \n
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.

\n \n

\n

Analysis written by: @awice

\n