Maximum Width binary tree

Question

Here is my code for the LeetCode problem

For a given binary tree, find the maximum width of the binary tree. The width of one level is defined as the length between the end-nodes even if there are None nodes in between

My code (in PyCharm) passess all the given tests but does not seem to pass on the LeetCode website. I am not sure why this is, so please don't try plugging it into the website as I assume the way I have built a binary tree is different to their method.

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    level_width = {0: [0, 0]}

    def get_width(self, root, level=0, pointer=1):
        if root.left:
            if level + 1 not in self.level_width:
                self.level_width[level + 1] = [pointer * 2, 0]
            self.level_width[level + 1][0] = min(self.level_width[level + 1][0], pointer * 2)
            self.get_width(root.left, level + 1, pointer * 2)
        if root.right:
            if level + 1 not in self.level_width:
                self.level_width[level + 1] = [9999, pointer * 2 + 1]
            self.level_width[level + 1][1] = max(self.level_width[level + 1][1], level + 1, pointer * 2 + 1)
            self.get_width(root.right, level + 1, pointer * 2 + 1)
        return

    def widthOfBinaryTree(self, root):
        """
          :type root: TreeNode
          :rtype: int
          """
        self.get_width(root)
        max_distance = 1
        for k, v in self.level_width.items():
            max_distance = max(max_distance, v[1] - v[0] + 1)
        return max_distance


root = Node(1)
root.left = Node(3)
root.left.left = Node(5)
root.left.left.left = Node(6)
root.right = Node(2)
root.right.right = Node(9)
root.right.right.right = Node(7)

print(root.widthOfBinaryTree(root))

Answer 1

In the above code, you missed counting the in-between null nodes, that is why, the result is wrong for the input [2,1,4,3, null,5].

You approached the problem using DFS(Depth First Search) algorithm which is useful to find the height of a tree.

BFS (Breadth-first search) algorithm would be the best suitable choice for this problem.