.png)
DSA Series Chapter 20 : HEIGHT OF BINARY TREE(Python Version)
1. Objective
To compute the height of a Binary Tree in Python using a recursive Depth First Search (DFS) approach.
2. Definition of Height (Exam-Ready)
The height of a binary tree is the number of nodes on the longest path from the root node to the deepest leaf node.
* In this implementation, height is counted in nodes, not edges.
3. Example Binary Tree
1
/ \
2 3
/ \
4 5
Height Calculation
Longest path:
1 → 2 → 4Number of nodes = 3
Hence, Height = 3
4. Key Idea Behind Height Calculation
Compute height of left subtree
Compute height of right subtree
Take the maximum
Add 1 for the current node
5. Formula Used
height(node) = 1 + max(height(left), height(right))
Base Case
height(None) = 0
6. Node Class Definition
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
7. Height Function (Core Logic)
def height(root):
if root is None:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
8. Line-by-Line Explanation
def height(root):
Function returns the height of the tree
rootrepresents current node
if root is None:
return 0
Base condition
Empty tree has height 0
left_height = height(root.left)
Recursively calculate left subtree height
right_height = height(root.right)
Recursively calculate right subtree height
return max(left_height, right_height) + 1
Select longer path
Add 1 for current node
9. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def height(root):
if root is None:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Height of Binary Tree:", height(root))
10. Output
Height of Binary Tree: 3
11. Time and Space Complexity
Time Complexity
O(n) — every node is visited once
Space Complexity
O(h) — recursion stack
Worst case (skewed tree): O(n)
12. C vs Python Comparison (Height)
| Aspect | C | Python |
|---|---|---|
| Memory | Manual | Automatic |
| Function style | Procedural | Recursive |
| Base case | NULL | None |
| Complexity | O(n) | O(n) |
13. Common Student Mistakes
Returning
-1instead of0Forgetting
+1Mixing height in edges vs nodes
Using BFS unnecessarily
14. Exam-Oriented One-Liner
Height of a binary tree is calculated recursively as one plus the maximum of heights of its left and right subtrees.
15. Learning Outcome
After this post, students can:
Define height of binary tree correctly
Implement recursive height logic in Python
Analyze complexity
Avoid common exam mistakes
ALSO CHECK
ALSO CHECK
Comments
Post a Comment