CODEWITHSUNDEEP
algorithmpython-2.7graphtreebinary-tree
Mariya
Mariya

Reputation: 847

python ete2 binary tree get the sum of descendants values

I have a b*inary tree* where only leaves have string values (a,b,c,d,e) I want to c*oncatenate the values of these leaves and pass it to their ancestor* 

        0
     /     \
    2      3
   / \    / \
  1   a  d   e
 / \
b   c

eg.

1->value=bc 2->value=abc  3->value=de

what is the best way to perfrom this in python ete2 tree class

thanks in advance

Upvotes: 1

Views: 295

Answers (1)

jhc
jhc

Reputation: 1721

A very standard procedure would be to use a postorder iteration. In addition, ETE implements also the get_cached_content function, which facilitates a bit this type of computations. 

from ete2 import Tree
t = Tree("(((b,c), a), (d,e));")

print "Method 1: caching node content"
internal_node_content = t.get_cached_content(store_attr="name")
for node, content in internal_node_content.iteritems():
    if not node.is_leaf():
        print node, "\nConcat:", ''.join(content)


print "Method 2: post order iteration"
node2concat = {}
for node in t.traverse("postorder"):
    if not node.is_leaf():
        concat = ''.join([node2concat[ch] for ch in node.children])
        node2concat[node] = concat
        print node, "\nConcat:", concat
    else:
        node2concat[node] = node.name


#Method 1: caching node content
# 
#         /-b
#      /-|
#   /-|   \-c
#  |  |
#--|   \-a
#  |
#  |   /-d
#   \-|
#      \-e 
#Concat: acbed
# 
#   /-b
#--|
#   \-c 
#Concat: cb
# 
#      /-b
#   /-|
#--|   \-c
#  |
#   \-a 
#Concat: acb
# 
#   /-d
#--|
#   \-e 
#Concat: ed
#Method 2: post order iteration
# 
#   /-b
#--|
#   \-c 
#Concat: bc
# 
#      /-b
#   /-|
#--|   \-c
#  |
#   \-a 
#Concat: bca
# 
#   /-d
#--|
#   \-e 
#Concat: de
# 
#         /-b
#      /-|
#   /-|   \-c
#  |  |
#--|   \-a
#  |
#  |   /-d
#   \-|
#      \-e 
#Concat: bcade

Upvotes: 2

Related Questions