Counting nodes in General tree in python

Question

I have created a Tree structure that is not a binary tree and having difficulties in getting the correct node count.

class TreeNode(object):
  def __init__(self, name='root', children=None,Parent=[]):
    self.Name = name
    self.Parents=Parent

    self.Children = []
    if children is not None:
        for child in children:
            self.add_child(child.Name)

 def __repr__(self):
   return self.Name

 def add_child(self, node):    
  self.Children.append(node)

and this is the latest in what I have tried to do in order to count the number of nodes in the tree.

def countNodes(Tree):      

   for Child in Tree.Children:
      return countNodes(Child)+1

   return 1

Could someone explain why this doesn't work? EDIT: I should clarify, When I say doesn't work it gives me a completely wrong count for he number of nodes in my graph.

what is wrong ? it is giving you a bad answer or an execution error ? — levi, Jan 28 '15 at 06:14
Beware of using lists as default arguments, eg `Parent=[]`. See http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument — PM 2Ring, Jan 28 '15 at 06:48

score 1 · Accepted Answer · answered Jan 28 '15 at 06:21

1

You countNodes function is not well. A parent node can have two childs, if you put a return statement within the for loop, it will return on the first child count and the second child count will be missing. You need to do something like this:

def countNodes(Tree):      
   count = 1
   for Child in Tree.Children:
      count +=  countNodes(Child)
   return count

answered Jan 28 '15 at 06:21

levi

22,001
7
73
74

yep, thats what i was missing. thanks works like a charm – Belrouk Jan 28 '15 at 06:24

score 0 · Answer 2 · answered May 12 '20 at 19:08

Just to add @levi has missed an edge case where root is None

so the modified code will be :

def numNodes(root):
    if root == None:
        return 0 
    node = 1
    for child in root.children:
        node = node + numNodes(child)
    return node

Counting nodes in General tree in python

2 Answers2