Solution by pingu92


  • 0
    P

    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.


Log in to reply
 

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