Python: A recursive function that counted up the total number of leaves in a BNT
ID: 3683545 • Letter: P
Question
Python: A recursive function that counted up the total number of leaves in a BNT:
Answer the following questions about this function definition.
a) Explain in your own words why we decided to always return 1 in the base case.
b) Explain what tree[0] and tree[1] represent in the recursive case.
c) Why can't you write tree[0] in the base case?
d) What do count_leaves(tree[0]) and count_leaves(tree[1]) represent in the recursive case?
e) Why did we decide to add count_leaves(tree[0]) + count_leaves(tree[1])?
f) Write a recursive function called add_leaves() that takes a Binary-Number-Tree and returns the sum of all the values of all of its leaves. For example, tree1 = ((1,(2,3)),4) would result in 10. Remember that this is a recursive function, so no loops and no lists!
Explanation / Answer
Basic Idea:
Identify all the leaves of a BTree
If a node has no children, it is a leaf.
If a node does have children, it is not a leaf. Count the number of leaves on the left BTree and the number of nodes on the right BTree and add them up.
Termination condition
– At some point recursion has to stop
– For example, don’t go beyond leafs
• Leafs don’t have children, referring to children leafs causes algorithm to crash
• Recursive call
– Algorithm calls itself on subsets of the input data
– One ore more recursive calls
• For binary tree we had two recursive calls, one for each child.
Sample function to add leaves-
# This function return sum of all left leaves in a
# given binary tree
def leftLeavesSum(root):
# Initialize result
res = 0
# Update result if root is not None
if root is not None:
# If left of root is None, then add key of
# left child
if isLeaf(root.left):
res += root.left.key
else:
# Else recur for left child of root
res += leftLeavesSum(root.left)
# Recur for right child of root and update res
res += leftLeavesSum(root.right)
return res
note-the above explanation and sample function can help to answer the given question.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.