CODEWITHSUNDEEP
pythontree-traversaltreepath
Charlie Baker
Charlie Baker

Reputation: 81

Counting all nodes of all paths from root to leaves

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.

Upvotes: 0

Views: 731

Answers (1)

Ryan
Ryan

Reputation: 2084

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).

Upvotes: 0

Related Questions