Teaching Kids Programming – Breadth First Search Algorithm to Compute the Max Width of a Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the maximum width of any level in the tree. The width of a level is the number of nodes that can fit between the leftmost node and the rightmost node.

Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in root

Hints:
BFS
left_child = 2parent
right_child = 2parent+1

Compute the Max Level Width of Binary Tree using Breadth First Search Algorithm

In order to compute the width of a level, we need to know the coordinate of the left-most and right-most Node. The coordinate for a left node equals to the double of its parent, and a right node equal the parent*2+1.

Using Breadth First Search Algorithm, we can explore all nodes on a same level, and then sure we know the width for that level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreeMaxWidth(self, root):
        if root is None:
            return 0
        q = deque([(root, 0)])
        ans = 0
        while q:
            sz = len(q)
            left = math.inf
            right = -math.inf
            for _ in range(sz):
                cur, w = q.popleft()
                if cur.left:
                   q.append((cur.left, w * 2)) 
                if cur.right:
                   q.append((cur.right, w * 2 + 1))
                left = min(left, w)
                right = max(right, w)
            ans = max(ans, right - left + 1)
        return ans

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreeMaxWidth(self, root):
        if root is None:
            return 0
        q = deque([(root, 0)])
        ans = 0
        while q:
            sz = len(q)
            left = math.inf
            right = -math.inf
            for _ in range(sz):
                cur, w = q.popleft()
                if cur.left:
                   q.append((cur.left, w * 2)) 
                if cur.right:
                   q.append((cur.right, w * 2 + 1))
                left = min(left, w)
                right = max(right, w)
            ans = max(ans, right - left + 1)
        return ans

The time complexity is O(N) and so is the space complexity – where N is the number of the nodes in the given binary tree.

Compute the Max Width of a Binary Tree:

• Teaching Kids Programming – Breadth First Search Algorithm to Compute the Max Width of a Binary Tree
• Breadth First Search Algorithm to Compute the Max Width of a Binary Tree
• Teaching Kids Programming – Depth First Search Algorithm to Compute the Max Width of a Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —