Count the nodes that have no children.
What to build
A short recursive function over a tree.
Requirements
- Complete
count_leaves(node). - Do not change the code that builds the tree.
Input
The first line has n. The second line has n different whole numbers.
Output
One number.
Constraints
n is from 1 to 200.
Example
Input:
4
5 3 8 1
Output:
2
Why it works
A node with no children counts as 1, and any other node's total is simply the sum for its two subtrees.
Examples
Example 1 · Input
4 5 3 8 1
Expected output
2
Example 2 · Input
1 7
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A leaf has no left child and no right child.
Hint 2
An empty tree has 0 leaves. Otherwise add the leaves of the two sides.
Solution
Show one correct solution (try it yourself first)
class Tree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Tree(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def count_leaves(node):
if node is None:
return 0
if node.left is None and node.right is None:
return 1
return count_leaves(node.left) + count_leaves(node.right)
n = int(input())
root = None
for v in input().split():
root = insert(root, int(v))
print(count_leaves(root))