Recursively Navigating Through Tree In Python

Question

I am to implement a length method for a custom Phylogenetic Tree class so we can call len(TreeObject) on it. The length of a tree is defined by how many leafs it has. A leaf means that node has no children. 'self.children' is equal to a list of tuples (node, weight) of that nodes children. I am very close I believe:

 def __len__(self):

# everytime it reaches the base case I should add 1
    if self.isLeaf():
        print('base case - reached leaf!')
        return 1

    for t,w in self.children:  
        print('not leaf so sent through loop')
        numLeaves = len(t)

    return numLeaves

The code is reaching the if statement the correct number of times, e.g. if the length is 3 it outputs 'base case - reached leaf!' 3 separate times. I just need a way of adding those together and storing it in a variable.

zch · Accepted Answer · 2013-02-11 22:04:32Z

2

Very close indeed. You are just overwriting numLeaves instead of summing them:

numLeaves = 0
for t,w in self.children:  
    print('not leaf so sent through loop')
    numLeaves += len(t)

It can also be implemented differently:

sum(len(t) for (t,w) in self.children)

answered Feb 11, 2013 at 22:04

zch

15.4k3 gold badges43 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

logeyg Over a year ago

thank you so much. idk how I didn't see that sooner. also I appreciate the more elegant python bit, thanks.

Collectives™ on Stack Overflow

Recursively Navigating Through Tree In Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related