CSc 120: Count Interior Nodes (Recursive)
Expected Behavior
Write a recursive function count_interior(tree), where
tree is a binary tree, that returns a count of the number of nodes
that are interior nodes. An interior node is a non-leaf node.
Your function should work for empty trees, trees with one node, and trees
with many nodes.
Note: Write a function and not a method.
Programming Requirements
Solve this problem using recursion.
Examples
In the examples below, the tree argument is illustrated by its string representation, however the
actual argument is a tree object.
-
count_interior(tree) where tree is
None
return value: 0
-
count_interior(tree) where tree is
(6 (8 None None) (9 None None))
return value: 1
-
count_interior(tree) where tree is
(6 (8 None None) (4 None (2 None (9 None None))))
return value: 3
-
count_interior(tree) where tree is
(6 (2 (3 (8 None None) None) (4 None None)) (9 None (12 (5 None None) (16 None (14 None None)))))
return value: 6