Python BFS early pruning


  • 0
    W

    We can use a standard bfs to find the second minimum value, but given the fact that the root value is the smaller of both its children, we can prune this early because we do not need to further than a node that has greater value of the root value.

    def findSecondMinimumValue(self, root):
        if not root or not root.left: return -1
        s = [root]
        smallest = float('inf')
        while s:
            temp = []
            for i in s:
                if i.val > root.val:
                    smallest = min(smallest, i.val)
                elif i.left:
                    temp.append(i.left)
                    temp.append(i.right) 
            s = temp
        return -1 if smallest == float('inf') else smallest

Log in to reply
 

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