Python solution with detailed explanation


  • 0
    G

    Second Minimum Node In a Binary Tree https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/description/

    Using BFS for second minimum

    • The root is the minimum value.
    • Beginning from second level, the smallest value from the root is a candidate for second minimum.
    • Now if there is no value on a level which is same as the root, then the second minimum value is the minimum value of that level. Otherwise, the minimum level is just a potential candidate. We need to continue searching until we find a level which has no value different from the root, or we exhaust all the levels.
    from collections import deque
    class Solution:
        def findSecondMinimumValue(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return -1
            dq = deque()
            second_val = float('inf')
            if root.left:
                dq.append(root.left)
                dq.append(root.right)            
            while dq:
                root_value_found = False
                for _ in range(len(dq)):
                    x = dq.popleft()
                    if root.val < x.val < second_val:
                        second_val = x.val
                    elif x.val == root.val:
                        root_value_found = True
                    if x.left:
                        dq.append(x.left)
                        dq.append(x.right)                    
                if second_val != float('inf') and not root_value_found:
                    return second_val
            return second_val if second_val != float('inf') else -1
    

    DFS Based Search

    class Solution:
        def findSecondMinimumValue(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return -1
            second_min = float('inf')
            def helper(x, min_val, t):
                if min_val < x.val < t[0]:
                    t[0] = x.val
                if x.left:
                    helper(x.left, min_val, t)
                    helper(x.right, min_val, t)
                return
            t = [second_min]
            helper(root, root.val, t)
            second_min = t[0]
            return second_min if second_min != float('inf') else -1
    

Log in to reply
 

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