Diameter of a Binary Tree | A binary tree node ; The function Compute the " height " of a tree . Height is the number of nodes along the longest path from the root node down to the farthest leaf node . ; Base Case : Tree is empty ; If tree is not empty then height = 1 + max of left height and right heights ; Function to get the diameter of a binary tree ; Base Case when tree is empty ; Get the height of left and right sub - trees ; Get the diameter of left and right sub - trees ; Return max of the following tree : 1 ) Diameter of left subtree 2 ) Diameter of right subtree 3 ) Height of left subtree + height of right subtree + 1 ; Constructed binary tree is 1 / \ 2 3 / \ 4 5 ; Function Call
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def height ( node ) : NEW_LINE INDENT if node is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT return 1 + max ( height ( node . left ) , height ( node . right ) ) NEW_LINE DEDENT def diameter ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT lheight = height ( root . left ) NEW_LINE rheight = height ( root . right ) NEW_LINE ldiameter = diameter ( root . left ) NEW_LINE rdiameter = diameter ( root . right ) NEW_LINE return max ( lheight + rheight + 1 , max ( ldiameter , rdiameter ) ) NEW_LINE DEDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 5 ) NEW_LINE print ( diameter ( root ) ) NEW_LINE