Approach #1 BreadthFirst 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 breadthfirst search
traversal may be a good idea to explore here.
Algorithm
Suppose we have a function def findSecondMinimumValue(self, root):
, we can perform the breadthfirst 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.