Sponsored
Sponsored
To solve the problem, we can perform a level order traversal (breadth-first search) of the tree using a queue. Each node will be annotated with a position value, starting with the root being assigned the position 0. As we traverse each level, we calculate the width as the difference between the position of the last node and the first node of that level plus one. This approach ensures that we take into account null positions that would exist in a perfect binary tree.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed exactly once.
Space Complexity: O(w), where w is the maximum width of the tree, held in the queue at any level.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def widthOfBinaryTree(self, root: TreeNode) -> int:
11 if not root:
12 return 0
13 queue = deque([(root, 0)])
14 max_width = 0
15 while queue:
16 level_length = len(queue)
17 _, first_pos = queue[0]
18 for i in range(level_length):
19 node, pos = queue.popleft()
20 if node.left:
21 queue.append((node.left, 2 * pos))
22 if node.right:
23 queue.append((node.right, 2 * pos + 1))
24 _, last_pos = queue[-1] if queue else (None, 0)
25 max_width = max(max_width, last_pos - first_pos + 1)
26 return max_width
27This Python solution uses a queue to perform a level order traversal. Each node's position is calculated by multiplying its parent position by 2 and adding 1 for right children. The width of each level is calculated using the positions assigned to each node.
An alternative approach involves using depth-first search (DFS) to traverse the tree while maintaining a map of the first position of each level. By keeping track of each node’s depth and position, we can determine the width of any tree level by computing the difference between the first and the current node's position at that depth.
Time Complexity: O(n), visiting each node recursively.
Space Complexity: O(d), where d is the max depth of the tree, accounting for the recursion stack.
1class Solution:
2 def widthOfBinaryTree(
This Python solution implements DFS to visit each node, mapping each level's first node position. We calculate width by comparing the position of the current node to this first node's position at each level.