1
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Please tag your Python questions with python and python-3.x. \$\endgroup\$ – Peilonrayz Jul 7 at 22:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Reinderien Jul 8 at 1:04
  • \$\begingroup\$ 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 \$\endgroup\$ – EML Jul 8 at 7:01
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.