Maximum Width of Binary Tree
- 2 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- Use the indexing technique from Binary Heap and Breadth-first Search
- I.e. a node's left child's number would be
2 * i, right child would be2 * i + 1 - In binary heap, these are array indexes. For our purposes, these are sorta the same. We can ignore the actual value of the nodes themselves, it is these "indexes" that are important
- When you do this, you can get a width of a level by subtracting the "index" of the rightmost node with the leftmost node and then adding 1, because that's how math works.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
max_width = 0
q = deque([(root, 1, 1)]) # (node, number, level)
while q:
first_number = None
for i in range(len(q)):
node, number, level = q.popleft()
if first_number is None:
first_number = number # Left-most node
if node.left:
q.append((node.left, 2 * number, level + 1))
if node.right:
q.append((node.right, 2 * number + 1, level + 1))
# Instead of extra logic for lastnode, just do maximum width calculation at each step
max_width = max(max_width, number - first_number + 1)
return max_width
Bad solution (works, TLE)
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
max_width = 1
q = deque([root])
while q:
atleast_one_left = False
first, last = None, None # index in level to calculate width
for i in range(len(q)):
node = q.popleft()
if node.val != 'N':
atleast_one_left = True
if first is None:
first = i
last = i
q.append(node.left if node.left else TreeNode('N'))
q.append(node.right if node.right else TreeNode('N'))
if last:
level_width = last - first + 1
max_width = max(max_width, level_width)
if not atleast_one_left:
break
return max_width