Child-parent collection(sort of tree)

Question

I need some sort of tree collection that is able to store basic child-parent relationships and next simple operations:

IsParent(thisNode, otherNode) (recursively one of any level parents)
IsChild(thisNode, otherNode) (recursively one of any level child's)
GetLevel(node) Get the level of a node.

This collection should be fast and can be immutable I don't need to change the tree. There are o lot of trees collection and I don't know what kind of tree do I need.

Do you know such collection in Python?

Possible duplicate of [Looking for a good Python Tree data structure](http://stackoverflow.com/questions/3009935/looking-for-a-good-python-tree-data-structure) — wildwilhelm, Jan 03 '17 at 14:43
@wildwilhelm I don't know what kind of tree type I need.. there are a lot of types — Brans Ds, Jan 03 '17 at 14:51

score 0 · Answer 1 · answered Jan 03 '17 at 14:26

I think you'll have to write your own. It's pretty easy though

class Tree:

    def __init__(self, data, parent=None):
        self.children = []
        self.parent = parent
        self.data = data

    def add_child(self, data):
        self.children.append(Tree(data, self))

    def has_child(self, target):
        return any(map(lambda x: x.data == target or x.has_child(target), self.children))

    def has_parent(self, target):
        return (self.parent.data == target or self.parent.has_parent(target)) if self.parent else False

I wouldn't worry overmuch about speed at this point. There are likely some ways of speeding this up a little bit, but a data structure like this is relatively lightweight. If you really do need something fast, then your best bet is to write it in C and then access it in python. That's probably overkill for your purposes.

Isn't this a recursion inside lamda that can fail with out of memory for deep tree with a lot of levels? — Brans Ds, Jan 03 '17 at 14:33
@BransDs I'm not aware of a different recursion depth for lambda functions, but it's possible I just don't know about it. If that's a concern, then I would recommend writing an iterative function that does something similar. How big do you want this thing? I think the default recursive depth is something like 1000 levels (a little less because of overhead). If your tree has any width at all and is that size it's going to be a real monster — Patrick Haugh, Jan 03 '17 at 14:40

Child-parent collection(sort of tree)

1 Answers1