CODEWITHSUNDEEP
python
Janbure
Janbure

Reputation: 79

Traversing a non-binary tree

I've made custom class for nodes

class NodeTree(object):
    def __init__(self, name = None, children = None):
        self.name = name
        self.children = children

and defined a function that make a tree(a node containing its children nodes)

def create_tree(d):
    x = NodeTree()
    for a in d.keys():
        if type(d[a]) == str:
            x.name = d[a]
        if type(d[a]) == list:
            if d[a] != []:
                for b in d[a]:
                    x.add_child(create_tree(b))
    return x

The input is a dict with one argument for the node name and a list with its children in the same form as the parent. The function work fine and I've made method that prove it but I can't find a way to traverse it right and get the height of the tree. I don't know if "height" it's the right term cause I know it may be ambivalent, I need to count the node as a measure unit, like this:

                                      parent
                                         |
                                         |
                                     ---------
                                     |       |
                                    child   child

The height of this tree is 2, I've tried everything, from counters to tag in the class, everything seems to degenerate an I never get the right height. How should I approach that?

Upvotes: 5

Views: 7084

Answers (1)

Blckknght
Blckknght

Reputation: 104712

To create a recursive height method for your tree that determines the height of the node (that is, the maximum number of nodes in a path from that node to a leaf):

def height(self):
    if not self.children:  # base case
        return 1
    else:                  # recursive case
        return 1 + max(child.height() for child in self.children)

Other tree traversals can also be done recursively. For example, here's a generator method that yields the names of the trees nodes in "pre-order" (that is, with each parent preceding its children and decedents):

def preorder(self):
    yield self.name
    for child in self.children:
        yield from child.preorder() # Python 3.3 only!

The yield from syntax in that loop is new in Python 3.3. You can get the same results in earlier versions with this:

        for descendent in child.preorder():
            yield descendent

Upvotes: 5

Related Questions