Approach #1 Breadth-First Search (BFS) [Accepted]
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.
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,
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)
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.