.png)
[Follow here] for daily coding insights
DSA Series Chapter 11
SOLUTIONS TO ALL 15 TREE TRAVERSAL EXERCISES(Python Version)
SECTION A – BASIC LEVEL
Q1
Tree:
A
/ \
B C
/ \
D E
Preorder: A B D E C
Postorder: D E B C A
Level-Order: A B C D E
Q2
Tree:
12
/ \
7 25
/ \
3 9
Preorder: 12 7 3 9 25
Q3
P
/ \
Q R
/ \
S T
Postorder: Q S T R P
Q4
X
/ \
Y Z
/ \
M N
Level-Order: X Y Z M N
Q5
8
/ \
3 10
/ \
1 6
Preorder: 8 3 1 6 10
Postorder: 1 6 3 10 8
SECTION B – INTERMEDIATE LEVEL
Q6
4
/ \
2 7
/ \ \
1 3 9
Inorder: 1 2 3 4 7 9
Preorder: 4 2 1 3 7 9
Postorder: 1 3 2 9 7 4
Q7
15
/ \
10 20
/ \ /
5 12 18
Postorder: 5 12 10 18 20 15
Q8
A
/ \
B C
\ / \
D E F
Level-Order: A B C D E F
Q9
25
/ \
15 40
/ \ \
10 20 50
Preorder: 25 15 10 20 40 50
Inorder: 10 15 20 25 40 50
Q10
K
/ \
L M
/ \ \
N O P
Postorder: N O L P M K
Level-Order: K L M N O P
SECTION C – ADVANCED LEVEL
Q11
Given:
Preorder: A B D E C F G
Inorder: D B E A F C G
Constructed tree:
A
/ \
B C
/ \ / \
D E F G
Postorder: D E B F G C A
Q12
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Preorder: 1 2 4 5 8 3 6 7
Inorder: 4 2 5 8 1 6 3 7
Postorder: 4 8 5 2 6 7 3 1
Level-Order: 1 2 3 4 5 6 7 8
Q13
H
/ \
I J
/ \ / \
K L M N
/
O
Level-Order: H I J K L M N O
Preorder: H I K L O J M N
Postorder: K O L I M N J H
Q14
90
/ \
50 120
\ \
60 150
/
130
Inorder: 50 60 90 120 130 150
Preorder: 90 50 60 120 150 130
Level-Order: 90 50 120 60 150 130
Q15
T
/ \
R W
/ / \
Q V X
\ /
S Y
Preorder: T R Q S W V X Y
Postorder: S Q R V Y X W T
Level-Order: T R W Q V X S Y
PYTHON VERSIONS – SOLUTIONS FOR ALL 15 QUESTIONS
Q1. Preorder Traversal of a Binary Tree (Recursive)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(node):
if node is None:
return
print(node.data, end=" ")
preorder(node.left)
preorder(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Preorder Traversal:")
preorder(root)
Q2. Inorder Traversal of a Binary Tree (Recursive)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)
print("Inorder Traversal:")
inorder(root)
Q3. Postorder Traversal (Recursive)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.data, end=" ")
root = Node(10)
root.left = Node(20)
root.right = Node(30)
print("Postorder Traversal:")
postorder(root)
Q4. Level Order Traversal Using Queue
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
from collections import deque
def level_order(root):
if root is None:
return
q = deque()
q.append(root)
while q:
temp = q.popleft()
print(temp.data, end=" ")
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
print("Level Order Traversal:")
level_order(root)
Q5. Count Total Nodes in Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_nodes(node):
if node is None:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Total Nodes:", count_nodes(root))
Q6. Count Leaf Nodes
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_leaf(node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return count_leaf(node.left) + count_leaf(node.right)
root = Node(5)
root.left = Node(10)
root.right = Node(15)
root.left.left = Node(20)
print("Leaf Nodes:", count_leaf(root))
Q7. Height of a Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
root = Node(1)
root.left = Node(2)
root.left.left = Node(3)
print("Height of Tree:", height(root))
Q8. Mirror Image of Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def mirror(node):
if node is None:
return
node.left, node.right = node.right, node.left
mirror(node.left)
mirror(node.right)
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.data, end=" ")
inorder(node.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
mirror(root)
inorder(root)
Q9. Search Key in Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def search(node, key):
if node is None:
return False
if node.data == key:
return True
return search(node.left, key) or search(node.right, key)
root = Node(10)
root.left = Node(20)
root.right = Node(30)
print("Found?" , search(root, 20))
Q10. Sum of All Nodes
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def sum_nodes(node):
if node is None:
return 0
return node.data + sum_nodes(node.left) + sum_nodes(node.right)
root = Node(5)
root.left = Node(10)
print("Sum:", sum_nodes(root))
Q11. Print Nodes at a Given Level
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def print_level(node, level):
if node is None:
return
if level == 1:
print(node.data, end=" ")
else:
print_level(node.left, level - 1)
print_level(node.right, level - 1)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Nodes at Level 2:")
print_level(root, 2)
Q12. Count Non-Leaf Nodes
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def count_non_leaf(node):
if node is None or (node.left is None and node.right is None):
return 0
return 1 + count_non_leaf(node.left) + count_non_leaf(node.right)
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
print("Non-leaf nodes:", count_non_leaf(root))
Q13. Maximum Value in Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_max(node):
if node is None:
return float('-inf')
return max(node.data, find_max(node.left), find_max(node.right))
root = Node(7)
root.left = Node(3)
root.right = Node(9)
print("Max value:", find_max(root))
Q14. Minimum Value in Binary Tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_min(node):
if node is None:
return float('inf')
return min(node.data, find_min(node.left), find_min(node.right))
root = Node(8)
root.left = Node(4)
root.right = Node(12)
print("Min value:", find_min(root))
Q15. Check if Two Trees Are Identical
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def is_identical(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return (
a.data == b.data and
is_identical(a.left, b.left) and
is_identical(a.right, b.right)
)
root1 = Node(1)
root1.left = Node(2)
root2 = Node(1)
root2.left = Node(2)
print("Identical?" , is_identical(root1, root2))
ALSO CHECK
ALSO CHECK
Comments
Post a Comment