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))

• Peilonrayz: Please tag your Python questions with python and python-3.x.
• Reinderien: This is treading a fine line: if you're asking for the community to identify and fix the test failure, then this doesn't belong on CodeReview, but rather StackOverflow. But if your intent is to disregard (for now) the test failure and improve the code in a generic sense, then you're OK here.
• MrJoe: Given I had referenced LeetCode I expected someone to check that website to confirm the performance of my code. I therefore wanted to warn anyone who looked at my code either to review it or to learn from it that this would not be beneficial as the code didn't pass Leetcode. I do not expect anyone to work out why it failed on Leetcode and am fully aware that requesting this is against site rules. I added the addendum that it passed on the Leetcode tests on my computer to let people know that this code does work. Thanks

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.