.png)
DSA Series Chapter 24 – DIAMETER OF BINARY TREE (Python Version Optimized – Single Traversal)
1. Objective
To compute the diameter of a binary tree using an optimized O(n) recursive approach implemented in Python.
2. Definition (Exam-Ready)
The diameter of a binary tree is the number of nodes on the longest path between any two leaf nodes in the tree.
📌 The path may or may not pass through the root.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Longest Path
4 → 2 → 1 → 3
Diameter
Nodes in longest path = 4
Diameter = 4
4. Why Optimized Approach?
Basic Approach Problem
Height is recomputed multiple times
Time complexity = O(n²)
Optimized Idea
Compute height and diameter together
Visit each node only once
5. Core Optimized Logic
At every node:
current_diameter = left_height + right_height + 1
update maximum diameter
return max(left_height, right_height) + 1
6. Binary Tree Node Class
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
7. Optimized Function to Compute Diameter
def diameter_of_tree(root):
diameter = [0] # Using list to simulate pass-by-reference
def height(node):
if node is None:
return 0
lh = height(node.left)
rh = height(node.right)
current_diameter = lh + rh + 1
if current_diameter > diameter[0]:
diameter[0] = current_diameter
return max(lh, rh) + 1
height(root)
return diameter[0]
8. Line-by-Line Explanation
diameter = [0]
List is used to allow updates inside nested function
def height(node):
Computes height while updating diameter
current_diameter = lh + rh + 1
Longest path passing through current node
diameter[0] = current_diameter
Updates global maximum diameter
return max(lh, rh) + 1
Returns subtree height
9. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def diameter_of_tree(root):
diameter = [0]
def height(node):
if node is None:
return 0
lh = height(node.left)
rh = height(node.right)
current_diameter = lh + rh + 1
if current_diameter > diameter[0]:
diameter[0] = current_diameter
return max(lh, rh) + 1
height(root)
return diameter[0]
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Diameter of the binary tree:", diameter_of_tree(root))
10. Output
Diameter of the binary tree: 4
11. Time and Space Complexity
Time Complexity
O(n)
Each node is visited exactly once.
Space Complexity
O(h) due to recursion stack
12. Important Exam Points
Diameter can be measured in nodes or edges
Always clarify question requirement
Optimized approach preferred in interviews
Path may bypass root
13. Common Beginner Mistakes
Confusing diameter with height
Forgetting
+1for current nodeUsing global variables unnecessarily
Returning diameter instead of height
14. Comparison: C vs Python Approach
| Aspect | C | Python |
|---|---|---|
| Reference | Pointer | List |
| Traversal | Single | Single |
| Complexity | O(n) | O(n) |
15. Learning Outcome
After this post, learners can:
Implement optimized diameter algorithm
Analyze tree properties efficiently
Solve interview-level problems
Write clean recursive Python code
ALSO CHECK
ALSO CHECK
Comments
Post a Comment