Save path from leaves to root using ete2

Question

I have a large tree where I want to get for each leaf node the path (all nodes) till the root.

I'm trying to do this using ete2 but the tree is so large and it seems to be too slow.

Can anyone suggest a faster way to do so?

thats what I'm doing:

    tr = Tree("anytree.nw", format=8)
    path_leaf_root = {} ## all paths from leafs to root
    root = tr.get_tree_root()
    for le in tr:
        if not path_leaf_root.has_key(le.name):
            path_leaf_root[le.name]=[]
        le_up = le
        while not le_up.name == root.name:
            le_up=le.up
            path_leaf_root[le.name].append(le_up.name)

Answer 1

You could try the following approach, which traverses the tree only once. In my computer, it processed a 50k tips tree in 0.24secs (a bit longer if you print or write the results):

from ete2 import Tree
t = Tree()
t.populate(50000)

import time
t1 = time.time()
current_path = [t]
for postorder, node in t.iter_prepostorder():
    if postorder:
        current_path.pop(-1)
    else:
        if not node.children:
            # print node.name, "path :", current_path
            pass
        else:
            current_path.append(node)
print time.time() - t1

# 0.242053985596