# Solution by pingu92

• #### Approach #1 Breadth-First Search (BFS) [Accepted]

Intuition

We have a tree with the special property that root will have the smaller value of the child nodes and this is also applicable to the subtree as well. So this make the root of the tree the smallest of all. So all we need to `find is a smallest value in a tree greater than the root`.

The structure of this special tree is such that it is quite possible that the solution node lies at the top levels, so using breadth-first search
traversal may be a good idea to explore here.

Algorithm

Suppose we have a function `def findSecondMinimumValue(self, root):`, we can perform the breadth-first search and simultaneously keep an eye on smallest element found so far, neglecting the root (which is the smallest of all, due to nature of the tree). Remember we can't simply return once `min_cur` changes once because it's possible that solution node is in the lower levels.
Take the following example for instance,
`[1,1,3,1,1,3,4,3,1,1,1,3,8,4,8,3,3,1,6,2,1]`

Python

``````def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return -1
queue, min_cur = [root], float("inf") # setting the min_cur to largest value
while len(queue):
current = queue.pop(0)
# print(queue, min_cur, current.val)
if current.val < min_cur and current.val != root.val:
min_cur = current.val
if current.left is not None:
queue.append(current.left)
if current.right is not None:
queue.append(current.right)
return -1 if min_cur == float("inf") else min_cur # if min_cur hasn't changed then tree has just single unique element(== root.val)

``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$. Where n is the number of nodes in the tree.
Since we traverse the entire tree just once, the complexity is \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$. We are storing the second minimum in a variable, and it takes an only constant amount of space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.