Method to count interior nodes of a binary tree 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
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