.png)
DSA Series Chapter 15 – POSTORDER TRAVERSAL (BINARY TREE)(Python Version)
1. Postorder Traversal – Quick Recall
Traversal Order:
Left → Right → Root
Category:
Depth First Traversal (DFS)
2. Binary Tree Used (Same as C Version)
1
/ \
2 3
/ \
4 5
1
/ \
2 3
/ \
4 5
Expected Postorder Output
4 5 2 3 1
4 5 2 3 1
3. Node Structure in Python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
4. Postorder Traversal Logic (Plain English)
If the current node is None, return
Traverse the left subtree
Traverse the right subtree
Visit (print/process) the root node
If the current node is None, return
Traverse the left subtree
Traverse the right subtree
Visit (print/process) the root node
5. Python Function – Recursive Postorder Traversal
def postorder(root):
if root is not None:
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
def postorder(root):
if root is not None:
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
6. Complete Executable Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder(root):
if root is not None:
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
# Tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Postorder Traversal:")
postorder(root)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder(root):
if root is not None:
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
# Tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Postorder Traversal:")
postorder(root)
Output
Postorder Traversal:
4 5 2 3 1
Postorder Traversal:
4 5 2 3 1
7. Dry Run (Recursive Call Flow)
postorder(1)
└── postorder(2)
└── postorder(4) → print 4
└── postorder(5) → print 5
→ print 2
└── postorder(3) → print 3
→ print 1
postorder(1)
└── postorder(2)
└── postorder(4) → print 4
└── postorder(5) → print 5
→ print 2
└── postorder(3) → print 3
→ print 1
8. Time and Space Complexity
Time Complexity
O(n) — every node is visited once
O(n) — every node is visited once
Space Complexity
O(h) — recursion stack
where h = height of the tree
Skewed tree → O(n)
Balanced tree → O(log n)
O(h) — recursion stack
where h = height of the tree
Skewed tree → O(n)
Balanced tree → O(log n)
9. Very Important Application (Exam-Oriented)
Postorder traversal is used to delete/free a binary tree.
Postorder traversal is used to delete/free a binary tree.
Reason:
Children nodes are processed before their parent, avoiding dangling references.
10. Common Student Mistakes
Printing root before right subtree (turns into inorder)
Forgetting base condition (root is None)
Confusing postorder with preorder
Printing root before right subtree (turns into inorder)
Forgetting base condition (root is None)
Confusing postorder with preorder
11. Practice Questions
Write postorder traversal for a left-skewed tree.
Predict postorder output for a single-node tree.
Why is postorder traversal ideal for deleting trees?
Convert recursive postorder traversal to iterative logic in Python.
Write postorder traversal for a left-skewed tree.
Predict postorder output for a single-node tree.
Why is postorder traversal ideal for deleting trees?
Convert recursive postorder traversal to iterative logic in Python.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment