Python, Straightforward BFS and DFS solutions


  • 11

    The main idea with this question is we will give each node a position value. If we go down the left neighbor, then position -> position * 2; and if we go down the right neighbor, then position -> position * 2 + 1. This makes it so that when we look at the position values L and R of two nodes with the same depth, the width will be R - L + 1.

    From there, we have two choices for traversals: BFS or DFS. In a BFS, all the nodes with the same depth are searched adjacent to each other, so we only need to remember the first and last positions seen for each depth.

    def widthOfBinaryTree(self, root):
        queue = [(root, 0, 0)]
        cur_depth = left = ans = 0
        for node, depth, pos in queue:
            if node:
                queue.append((node.left, depth+1, pos*2))
                queue.append((node.right, depth+1, pos*2 + 1))
                if cur_depth != depth:
                    cur_depth = depth
                    left = pos
                ans = max(pos - left + 1, ans)
    
        return ans
    

    It might be more natural to attempt a DFS. Here, we create a dfs iterator that yields the depth and position of each node.

    After, we need to know for each depth, what was the leftmost position left[depth] and the rightmost position right[depth]. We'll remember the largest width as we iterate through the nodes.

    def widthOfBinaryTree(self, root):
        def dfs(node, depth = 0, pos = 0):
            if node:
                yield depth, pos
                yield from dfs(node.left, depth + 1, pos * 2)
                yield from dfs(node.right, depth + 1, pos * 2 + 1)
    
        left = {}
        right = {}
        ans = 0
        for depth, pos in dfs(root):
            left[depth] = min(left.get(depth, pos), pos)
            right[depth] = max(right.get(depth, pos), pos)
            ans = max(ans, right[depth] - left[depth] + 1)
    
        return ans
    

Log in to reply
 

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