Traversing a non-binary tree

Question

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?

Did you check if the tree contains actually what you think? For example by prettyprinting? — Sebastian
– Sebastian, Commented Dec 5, 2012 at 19:02
Getting the tree depth by recursion should be quite easy: just add 1 to the depth of the deepest sub tree. Use the "max" function. — Sebastian
– Sebastian, Commented Dec 5, 2012 at 19:04

Seanny123 · Accepted Answer · 2017-02-24 04:10:29Z

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

Thank you very much, that is very interesting and precise, I didn't thought about max() cause my tree is not binary and it takes only 2 argument, also I did not know that I could pass a for as argument! Doing a little research would have saved me a lot of struggle.
@Janbure Look at max() doc and you'll see that it has two signatures: a single iterable argument(like this case) or n arguments(so they can be more than 2). You can also specify a keyword only parameter key, just like in sort.
@Janbure: That max call uses what's known as a "generator expression". They're really handy for creating an iterable object on the fly.

Collectives™ on Stack Overflow

Traversing a non-binary tree

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related