text: 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.