Search code examples
pythonalgorithmdata-structuresgraphbinary-tree

Diameter of binary tree fails 4 out of 104 test cases

I am working on Leet Code problem 543. Diameter of Binary Tree:

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1

enter image description here

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

This is my attempt:

def diameterOfBinaryTree(self, root):
    return self.getHeight(root.left) + self.getHeight(root.right)

def getHeight(self, root):
    if not root:
        return 0
    return max(self.getHeight(root.left), self.getHeight(root.right)) + 1

I got 100/104 test cases passed.

The test case that I got wrong had an input of [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2] with an expected result of 8. However, due to the logics of my solution, I got 7 instead and have no idea how I could be wrong.

Solution

  • The only test case that I got wrong had an input of [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2] ... have no idea how I could be wrong.

    The provided tree looks like this:

                    ___4___
               /       \
             -7     ___-3_____
                   /          \
              ___-9___        -3
             /        \       /
            9         -7    -4
           /          / \
        __6__       -6  -6
       /     \      /   /
      0       6    5   9
       \     /        /
       -1  -4       -2

    The longest path is indeed 8, because the longest path in the subtree rooted at -9 has that longest path. Your code does not find that longest path because it requires that the root is part of it.

    So, you should check what the longest path is for any subtree (recursively) and retain the longest among these options:

    • The longest path found in the left subtree
    • The longest path found in the right subtree
    • The longest path that can be made by including the root (i.e. left-height + right-height + 1)

    Your code does not take the two first options into account and always goes for the third.

    The above is implemented in this (hidden) solution. First try it yourself:

    class Solution(object):
    def diameterOfBinaryTree(self, root):
    self.longestPath = 0

    def levels(node): # With side-effect: it updates longestPath
    if not node:
    return 0
    leftLevels = levels(node.left)
    rightLevels = levels(node.right)
    self.longestPath = max(self.longestPath, leftLevels + rightLevels)
    return 1 + max(leftLevels, rightLevels)

    levels(root) # Not interested in the returned value...
    return self.longestPath # ...but all the more in the side effect!