Problem description
Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.
The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.
Example 1:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
Example 2:
Input:
1
/
3
/ \
5 3
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
Example 3:
Input:
1
/ \
3 2
/
5
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
Example 4:
Input:
1
/ \
3 2
/ \
5 9
/ \
6 7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).
Solution
BFS
- We do level order traversal of the tree. For each node, we add additional information as the level it belongs and its x coordinate. Then for each level, we calculates the width as the difference of x coordinate between the rightmost node and leftmost node. The maximum difference among all the levels are the width of the binary tree
Below is python implementation
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
queue = collections.deque()
if not root:
return 0
queue.append((root,0,0))
ans = 1
left = right = None
while queue:
n = len(queue)
for i in range(n):
node, x, y = queue.popleft()
if node.left:
queue.append((node.left, 2 * x, y + 1))
if node.right:
queue.append((node.right, 2 * x + 1, y + 1))
if i == 0:
left = x
if i == n - 1:
right = x
ans = max(ans, right - left + 1)
return ans
DFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
levelboundary = {}
self.ans = 0
def dfs(root, x:int, y:int)->None: #x and y coordinate of current node
if not root:
return
if y in levelboundary:
if x < levelboundary[y][0]:
levelboundary[y][0] = x
if x > levelboundary[y][1]:
levelboundary[y][1] = x
else:
levelboundary[y] = [None, None]
levelboundary[y][0] = x
levelboundary[y][1] = x
self.ans = max(self.ans, levelboundary[y][1] - levelboundary[y][0] + 1)
dfs(root.left, 2*x, y + 1)
dfs(root.right, 2*x + 1, y + 1)
dfs(root, 0, 0)
return self.ans