Diameter of a Binary Tree in O ( n ) [ A new method ] | Tree node structure used in the program ; Function to find height of a tree ; update the answer , because diameter of a tree is nothing but maximum value of ( left_height + right_height + 1 ) for each node ; Computes the diameter of binary tree with given root . ; This will storethe final answer ; Driver code
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def height ( root , ans ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT left_height = height ( root . left , ans ) NEW_LINE right_height = height ( root . right , ans ) NEW_LINE ans [ 0 ] = max ( ans [ 0 ] , 1 + left_height + right_height ) NEW_LINE return 1 + max ( left_height , right_height ) NEW_LINE DEDENT def diameter ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = [ - 999999999999 ] NEW_LINE height_of_tree = height ( root , ans ) NEW_LINE return ans [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE print ( " Diameter ▁ is " , diameter ( root ) ) NEW_LINE DEDENT