Looking for a good Python Tree data structure [closed]

Posted on

Question :

Looking for a good Python Tree data structure [closed]

I am looking for a good Tree data structure class. I have come across this package, but since I am relatively new to Python (not programming), I dont know if there are any better ones out there.

I’d like to hear from the Pythonistas on here – do you have a favorite tree script that you regularly use and would recommend?


To clarify, by ‘Tree’, I mean a simple unordered tree (Hmm, thats a bit of a recursive definition – but hopefully, that clarifies things somewhat). Regarding what I need the tree for (i.e. use case). I am reading tree data from a flat file and I need to build a tree from the data and traverse all nodes in the tree.

Answer #1:

Roll your own. For example, just model your tree as list of list. You should detail your specific need before people can provide better recommendation.

In response to HelloGoodbye’s question, this is a sample code to iterate a tree.

def walk(node):
    """ iterate tree in pre-order depth-first search order """
    yield node
    for child in node.children:
        for n in walk(child):
            yield n

One catch is this recursive implementation is O(n log n). It works fine for all trees I have to deal with. Maybe the subgenerator in Python 3 would help.

Answered By: morpheous

Answer #2:

You can build a nice tree of dicts of dicts like this:

import collections

def Tree():
    return collections.defaultdict(Tree)

It might not be exactly what you want but it’s quite useful! Values are saved only in the leaf nodes. Here is an example of how it works:

>>> t = Tree()
>>> t
defaultdict(<function tree at 0x2142f50>, {})
>>> t[1] = "value"
>>> t[2][2] = "another value"
>>> t
defaultdict(<function tree at 0x2142f50>, {1: 'value', 2: defaultdict(<function tree at 0x2142f50>, {2: 'another value'})}) 

For more information take a look at the gist.

Answered By: Wai Yip Tung

Answer #3:

I found a module written by Brett Alistair Kromkamp which was not completed. I finished it and make it public on github and renamed it as treelib (original pyTree):


May it help you….

Answered By: Stefan

Answer #4:

Building on the answer given above with the single line Tree using defaultdict, you can make it a class. This will allow you to set up defaults in a constructor and build on it in other ways.

class Tree(defaultdict):
    def __call__(self):
        return Tree(self)

    def __init__(self, parent):
        self.parent = parent
        self.default_factory = self

This example allows you to make a back reference so that each node can refer to its parent in the tree.

>>> t = Tree(None)
>>> t[0][1][2] = 3
>>> t
defaultdict(defaultdict(..., {...}), {0: defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})})
>>> t[0][1].parent
defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})
>>> t2 = t[0][1]
>>> t2
defaultdict(defaultdict(..., {...}), {2: 3})
>>> t2[2]

Next, you could even override __setattr__ on class Tree so that when reassigning the parent, it removes it as a child from that parent. Lots of cool stuff with this pattern.

Answered By: caesar0301

Answer #5:

For a tree with ordered children, I’d usually do something kind of like this (though a little less generic, tailored to what I’m doing):

class TreeNode(list):

    def __init__(self, iterable=(), **attributes):
        self.attr = attributes
        list.__init__(self, iterable)

    def __repr__(self):
        return '%s(%s, %r)' % (type(self).__name__, list.__repr__(self),

You could do something comparable with a dict or using DictMixin or it’s more modern descendants if you want unordered children accessed by key.

Answered By: Sandy Chapman

Answer #6:

It might be worth writing your own tree wrapper based on an acyclic directed graph using the networkx library.

Answered By: Matt Anderson

Answer #7:

Here’s something I was working on.

class Tree:
    def __init__(self, value, *children):
        '''Singly linked tree, children do not know who their parent is.
        self.value = value
        self.children = tuple(children)

    def arguments(self):
        return (self.value,) + self.children

    def __eq__(self, tree):
        return self.arguments == tree.arguments

    def __repr__(self):
        argumentStr = ', '.join(map(repr, self.arguments))
        return '%s(%s)' % (self.__class__.__name__, argumentStr)

Use as such (numbers used as example values):
t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

Answered By: Andrew Walker

Answer #8:

Would BTrees help? They’re part of the Zope Object Database code. Downloading the whole ZODB package is a bit of overkill, but I hope the BTrees module would be at least somewhat separable.

Answered By: Aaron Robson

Leave a Reply

Your email address will not be published. Required fields are marked *