Teaching Kids Programming – Depth 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 Depth First Search Algorithm

Let’s perform a Depth First Search to traverse the binary tree and we can pass down the level and the position value along the Recursion. If we go to the left tree, we double the position value, and if we go to right node, we multiply the position value and then plus one. And we update the left most and right most position value for each level in a dictionary (hash map).

The result would be the maximum of (Right – Left + 1) for all levels.

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

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return 0
        data = {}
        def dfs(root, v, lvl):
            nonlocal data
            if root is None:
                return 
            if lvl in data:
                data[lvl][0] = min(data[lvl][0], v)
                data[lvl][1] = max(data[lvl][1], v)
            else:
                data[lvl] = [v, v]
            dfs(root.left, v * 2, lvl + 1)
            dfs(root.right, v * 2 + 1, lvl + 1)
        dfs(root, 0, 0)
        return max(r-l+1 for l,r in data.values())

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return 0
        data = {}
        def dfs(root, v, lvl):
            nonlocal data
            if root is None:
                return 
            if lvl in data:
                data[lvl][0] = min(data[lvl][0], v)
                data[lvl][1] = max(data[lvl][1], v)
            else:
                data[lvl] = [v, v]
            dfs(root.left, v * 2, lvl + 1)
            dfs(root.right, v * 2 + 1, lvl + 1)
        dfs(root, 0, 0)
        return max(r-l+1 for l,r in data.values())

The time complexity is O(N) and so is the space complexity where N is the number of the nodes for a 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) —