Welcome to the exciting world of Data Structures and Algorithms! Today, we're diving deep into understanding the Diameter of a Tree š. Let's get started!
A Tree is a type of data structure composed of nodes where every node has a parent node, except for the root node, which has no parent. Trees are used to represent hierarchical relationships and can be found in various real-world applications such as file systems, XML documents, and family trees.
The Diameter of a Tree is defined as the maximum distance between any two nodes in the tree. This distance is measured in terms of the number of edges.
To find the Diameter of a Tree, we can follow these steps:
Find the Height of the Tree: The height of a tree is the number of edges on the longest path from the root to any leaf.
Find the Diameter: The Diameter of a tree is either:
Let's write a Python function that calculates the Diameter of a given Binary Tree:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.data = key
def height(node):
if node is None:
return 0
else:
return 1 + max(height(node.left), height(node.right))
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, max(ldiameter, rdiameter))
# Create a Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("The Diameter of the Tree is:", diameter(root)):::quiz Question: What is the Diameter of the given Binary Tree?
1
/ \
2 3
/ \
4 5
A: 4 B: 5 C: 6 Correct: C Explanation: The Diameter is the maximum distance between any two nodes, which is 4 (from node 1 to node 5) in this case. However, the Diameter of the tree is the maximum of the Diameter of the left and right subtrees, which is 6 (maximum of 4 and 5).