# Python, Straightforward BFS and DFS solutions

• 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
``````

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