Method to count interior nodes of a binary tree

Question

I'm not a programmer, but am playing around with a binary tree Class in Python and would like help with a recursive method to count interior nodes of a given tree.

The code below seems to work, but is this solution the clearest, in terms of logic, for counting interior nodes? I'm keen that the code is the cleanest and most logical solution, whilst remaining recursive.

The qualifier for being an interior node, as far as I'm aware here is, that an interior node should have a parent, and at least one child node.

def count_interior_nodes(self, root):
 """Return number of internal nodes in tree"""
 if(root.parent == None):
 # Root node so don't count, but recurse tree
 return self.count_interior_nodes(root.left) + self.count_interior_nodes(root.right) + 0
 elif (root.left != None or root.right != None):
 # Has parent, but isn't leaf node, so count and recurse
 return self.count_interior_nodes(root.left) + self.count_interior_nodes(root.right) + 1
 else:
 # Leaf node, so return zero
 return 0

• Jeff Mercado: Just to get your head thinking about this, suppose we were at the root node (so parent == None), what would happen if one of the children were None?
• Alex2134: Hi @Jeff, All nodes have a left and right attribute, so leaf nodes would both be set to None in which case root.left == None and root.right == None and would return 0 up the recursion tree, this would be a base case wouldn't it? So zero would be added to the cumulative total.
• Jeff Mercado: I guess you need a specific example to see what I'm hinting at. Consider the tree where you have the root and it has a left child which is a leaf and no right child. So something like this: Tree(left = Tree(left = None, right = None), right = None). Step through this with your code (or run it) and see what happens.
• Loki Astari: The more classic way of implementing this recursively is not to care if you are the root. If you are NULL then it is 0. Otherwise it is 1 + Count(left) + Count(right). You can the wrap this with a function that prints information and calls Count(root).
• Alex2134: @Jeff, Is it that I haven't accounted for the exception where root == None? @Loki I'm looking to count interior nodes only, so the node must have a parent and should have at most one Null child node (i.e not interested in counting all nodes).

Answer 1

So after our little discussion, I hope you see that you're missing some key cases here, when the root given is None.

Some things that should be pointed out, when comparing to None, you should be checking if it is or is not None. Don't use (in)equality here, it is just not correct.

Assuming this is a method on your tree node objects, I'd rewrite this to make use of self. That way we don't even need to worry about the case when self is None, that just shouldn't happen.

def count_interior_nodes(self):
 count = 0
 hasLeft, hasRight = self.left is not None, self.right is not None
 if hasLeft:
 count += self.left.count_interior_nodes()
 if hasRight:
 count += self.right.count_interior_nodes()
 if (hasLeft or hasRight) and self.parent is not None:
 count += 1
 return count

• Alex2134: Hi @Jeff, thanks for the great advice. So when the root is None the count is returned? Good to make use of self as it is indeed a method of the Tree Node object. I didn't know and the rule when comparing None either, so I've gone through and corrected all my code on this note! I've also some other methods, such as get_height() I've also got them to make use of self. Great advice. Cheers Alex
• Jeff Mercado: In your code, the big issue is that when the root given is None, you'll get an attribute error on the None object (which is equivalent to a "NullReferenceException" in other languages). In that case, the count wouldn't be returned. In fact, nothing is returned since an exception was raised and unhandled. That should not be an issue when running the code I've provided. We can assume that self will always be set to an instance of your class so we avoid that case. We're also checking beforehand if the children are None so no chance of the attribute error.