Generate Binary Tree From String

Shane Dowling
Oct 27, 2015 · 1 min read

Recently while implementing the Small Parsimony Problem I had the need to generate a binary tree from a string in Python.

The pseudo-code in the question implicitly assumes you have some functionality that will generate a DNA sequence like CAAATCCC into a binary tree, then run SmallParsimony on it. I couldn’t find that functionality anywhere, so I decided to implement something simple in networkx. Hopefully it’s useful.

#!/usr/bin/env python
Shane Dowling, 27 Oct 2015
To run simply call generate_leaf_graph and pass in s string.
def count_predecessors(T):
pred = 0
for v in T.nodes():
pred += 1
return pred
def generate_leaf_graph(s):
Will generate a leaf graph and return it along
with the Character dictionary representing the characters
at each leaf node position
T = nx.DiGraph()
Character = {}
i = 0
parI = len(s)
for (son, daughter) in zip(s[0::2], s[1::2]):
Character[i] = son
Character[i+1] = daughter
T.add_edge(parI, i)
T.add_edge(parI, i+1)
i += 2
parI += 1
while count_predecessors(T) > 1:
for v in T.nodes():
T.add_edge(parI, v)
T.add_edge(parI, v+1)
parI += 1
return [T, Character]

Tech Blog

Random smattering of technical posts

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store