_662. Maximum Width of Binary Tree.md

662. Maximum Width of Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : October 28, 2024

Last updated : October 28, 2024

---

Related Topics : Tree, Depth-First Search, Breadth-First Search, Binary Tree

Acceptance Rate : 43.82 %

---

Solutions

• m662 bfs.py
• m662 dfs.py

Python

m662 bfs.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        nxt_nodes = deque([(root, 0, 0)])      # node, index, depth

        max_width = 0
        leftmost, rightmost = inf, -inf
        curr_depth = None
        while nxt_nodes :
            curr, indx, depth = nxt_nodes.popleft()
            if curr_depth != depth :
                max_width = max(max_width, rightmost - leftmost + 1)
                leftmost, rightmost, curr_depth = inf, -inf, depth

            if leftmost > indx :
                leftmost = indx
            if rightmost < indx :
                rightmost = indx

            if curr.left :
                nxt_nodes.append((curr.left, 2 * indx, depth + 1))
            if curr.right :
                nxt_nodes.append((curr.right, 2 * indx + 1, depth + 1))

        max_width = max(max_width, rightmost - leftmost + 1)
        return max_width

m662 dfs.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(curr: Optional[TreeNode],
                lvl_maxes: List[int],
                lvl_mins: List[int],
                curr_indx: int = 0,
                depth: int = 0) -> None :
            if not curr :
                return
            
            if depth >= len(lvl_maxes) :
                lvl_maxes.append(curr_indx)
            elif curr_indx > lvl_maxes[depth] :
                lvl_maxes[depth] = curr_indx
            
            if depth >= len(lvl_mins) :
                lvl_mins.append(curr_indx)
            elif curr_indx < lvl_mins[depth] :
                lvl_maxes[depth] = curr_indx
            
            dfs(curr.left, lvl_maxes, lvl_mins, curr_indx * 2, depth + 1)
            dfs(curr.right, lvl_maxes, lvl_mins, curr_indx * 2 + 1, depth + 1)
        
        lvl_maxes = []
        lvl_mins = []
        dfs(root, lvl_maxes, lvl_mins, 0, 0)
        return max([maxx - minn + 1 for maxx, minn in zip(lvl_maxes, lvl_mins)])