0

If given a tree with nodes with integers: 1 ~ 10, and branching factor of 3 for all nodes, how can I write a function that traverses through the tree counting from root to leaves for EVERY paths

So for this example, let's say it needs to return this:

{1: 1, 2: 5}

I've tried this helper function:

def tree_lengths(t):
    temp = []
    for i in t.children:
        temp.append(1)
        temp += [e + 1 for e in tree_lengths(i)]
    return temp

There are too many errors with this code. For one, it leaves behind imprints of every visited node in the traversal in the returning list - so it's difficult to figure out which ones are the values that I need from that list. For another, if the tree is large, it does not leave behind imprints of the root and earlier nodes in the path prior to reaching the line "for i in t.children". It needs to first: duplicate all paths from root leaves; second: return a list exclusively for the final number of each path count.

Please help! This is so difficult.

Charlie Baker
  • 81
  • 1
  • 2
  • 7
  • Are you trying to count the number of paths? or are you trying to list all paths? – inspectorG4dget Mar 31 '15 at 19:42
  • It is actually quite unclear what you are trying to achieve. For the example you told (1~10) what does the output `{1:1, 2:5}` mean? What are the keys and what are the values? – khajvah Mar 31 '15 at 19:46

1 Answers1

0

I'm not sure exactly what you are trying to do, but you'll likely need to define a recursive function that takes a node (the head of a tree or subtree) and an integer (the number of children you've traversed so far), and maybe a list of each visited node so far. If the node has no children, you've reached a leaf and you can print out whatever info you need. Otherwise, for each child, call this recursive function again with new parameters (+1 to count, the child node as head node, etc).

Ryan
  • 2,058
  • 1
  • 15
  • 29