Python program to find diameter of binary tree in O(n).
Description :
Diameter of binary tree is length of longest path between any two nodes in a tree.
This path may or may not pass through the root. The diameter of binary tree can be
calculated using only height function, because the diameter of binary tree is nothing
but the maximum value of (left_height+right_height+1)for each node.
So we need to calculate this value.
Program:
classnewNode:def__init__(self, data):
self.data = data
self.left = self.right = Nonedefheight(root, result):if (root == None):
return0
left_height = height(root.left, result)
right_height = height(root.right, result)
# update the answer, because diameter # of a tree is nothing but maximum # value of (left_height + right_height + 1) # for each node
result[0] = max(result[0], 1 + left_height + right_height)
return1 + max(left_height, right_height)
# Computes the diameter of binary # tree with given root. defdiameter(root):if (root == None):
return0
result = [-999999999999] # This will store # the final answer
height_of_tree = height(root, result)
return result[0]
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
print("Diameter is", diameter(root))
Comments