Python Program to Find the Diameter of a Binary Tree

This program calculates the diameter of a binary tree, which is the longest path between any two nodes. The program uses a depth-first search (DFS) approach, where for each node, the height of its left and right subtrees is calculated, and these values are used to determine the maximum path length at that node. The diameter at any node is the sum of the heights of its left and right subtrees.

class TreeNode:
    """Definition of a TreeNode for a Binary Search Tree (BST)."""
    def __init__(self, x):
        """
        Initialize the tree node with a value.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """Solution class to calculate the diameter of a binary tree."""
    def diameterOfBinaryTree(self, root):
        """
        Calculate the diameter of the binary tree.
        
        :param root: TreeNode, the root of the binary tree
        :return: int, the diameter of the tree
        """
        self.diameter = 0
        
        def depth(node):
            """
            Calculate the depth of the tree and update the diameter.
            
            :param node: TreeNode, the current node
            :return: int, the depth of the current subtree
            """
            if not node:
                return 0
            # Recursively find the depth of the left and right subtree
            left = depth(node.left)
            right = depth(node.right)
            
            # Update the diameter if the path through the current node is longer
            self.diameter = max(self.diameter, left + right)
            
            # Return the depth of the current subtree
            return max(left, right) + 1
        
        depth(root)
        return self.diameter

# Example Usage
if __name__ == "__main__":
    # Construct a simple tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    # Instance of Solution
    sol = Solution()
    
    # Find the diameter of the tree
    tree_diameter = sol.diameterOfBinaryTree(root)
    print(f"The diameter of the tree is: {tree_diameter}")

The program defines a class TreeNode to represent the nodes of the tree and a class Solution with a method diameterOfBinaryTree to compute the diameter. The method uses a nested function depth to traverse the tree and compute the depth of each subtree, updating the diameter as needed. The final diameter is determined by the maximum value obtained during the recursive traversal.