Search code examples
pythontreerecursive-datastructures

Diameter of the tree

I have a code to find the diameter of the tree. As per my understanding diameter is number of nodes in longest path between 2 leaf nodes.

The code is:

def diameter(root):
    if root is None:
        return 0
    lheight = height(root.left)
    rheight = height(root.right)

    ldiameter = diameter(root.left)
    rdiameter = diameter(root.right)
 
    return max(lheight + rheight + 1, max(ldiameter, rdiameter))

Where height is a function to calculate the height of the node. However, I feel there is no need to make recursive call to diameter function as shown in following snippet as it gives the same output.

def diameter(root):
    if root is None:
        return 0
    lheight = height(root.left)
    rheight = height(root.right)

    return lheight + rheight + 1

Why are the recursive calls to diameter needed in the first code?

Probably, I am unable to find the case where lheight + rheight + 1 is less than max(ldiameter, rdiameter).

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))
Solution

  • Recursive calls to diameter function are needed because diameter of the tree does not necessarily pass through the root of the tree.

    Your second piece of code just gives the result height(left subtree of root) + height(right subtree of root) + 1 which will be the correct answer if diameter "path" passes through root (but not always).

    An example of such tree is the 2nd tree in - enter image description here

    In the 2nd image above, if we apply your second code, we will get result as 7 but correct answer is 9 (if we consider diameter not passing through root)