How to iterate through instances in a tree?

Question

I have a problem with a self-written tree class in python:

class Tree:
    def __init__(self, parent=0, value=0):
        self.value = value
        self.parent = parent
    def __iter__(self): return self
    def next(self):
        tmp = self.value
        try:
            self.parent = self.parent.parent
            self.value = self.parent.value
        except AttributeError:
            raise StopIteration
        return tmp
    def sum(self):
        list_ = [item for item in self]
        print list_
        return sum(list_)

Actually, the "tree" is not fully written, but the current problem blocks further progress. The structure has only two instance variables (value, parent). I would like to sum values from the current instance to the first parent with iterators (if it is all together possible). The sum method is used for that (additional list_ variable is unnecessary, but helps further to explain the problem).

When running a test case

parent = Tree()
child = Tree(parent=parent, value=8)
child2 = Tree(parent=child,value=10)
print child2.sum()

I obtain the following:

[10]
10

Please, could anybody explain why the list of values contains only one number though it should look like [10,8]? Seems the problem is in the implementation of iter and next, but I can't understand how to repair the solution.

Thank you in advance.

item for item in self will only ever return self. The iteration needs to be following the self.parent until it is None which only happens at the root node - you probably need a yield to do this. Also your defaults for parent and value in the definition of __init__ MUST use None and not 0 as the default value. Also you aren't constructing a tree, this is a list of items linked by parent. To properly implement a tree, shouldn't each node include child1/child2 (or left/right) instance variables so the structure can be navigated away from the root as well as towards it? — DisappointedByUnaccountableMod, Oct 16 '16 at 16:42
To @barny: I do completely agree with you about `None` as the primary parent. The tree should contain children as well, but in my case there can be plenty of them. As I have written, this functionality has not been implemented because of the problem with iterators. Finally, iterating through self.parent is a good idea, although I couldn't implement it in a good manner. If `next` returns self.parent (even with `self = self.parent`), `sum` predictably falls into a neverending loop. If you would show an implementation with `yield`. it could be of much help. — , Oct 16 '16 at 17:08

Nf4r · Answer 1 · 2016-10-16T17:57:42.083

0

Here you go:

class Tree:
    def __init__(self, parent=None, value=0):
        self.value = value
        self.parent = parent

    def __iter__(self): 
        yield self.value
        root = self
        while root.parent is not None:
            yield root.parent.value
            root = root.parent
        raise StopIteration


    def tree_sum(self):
        return sum(list(self))


parent = Tree()
child = Tree(parent=parent, value=8)
child2 = Tree(parent=child,value=10)

I've changed the default parent value to None.

for i in child2:
    print(i)

10
8
0 # 0 is here because the parent value is 0 by default.

edited Oct 16 '16 at 17:57

answered Oct 16 '16 at 17:02

Nf4r

109
3

Every time you iterate through an instance of the class, you're building a list. This may not be desirable as the number of parents grow – Moses Koledoye Oct 16 '16 at 17:32

score 0 · Accepted Answer · edited May 23 '17 at 12:33

I'm not sure you can call this a Tree. One would expect parent node(s) and multiple leaf nodes, and not just a linear connection of objects.

See: A general tree implementation?

On another note, if you want to implement a linkedlist, suggestions made in the comment to your question by Barny should be considered and as well, you can give an eye to: Python Linked List

Coming to your current implementation, you'll need some sort of loop, to walk from the current child node up until the head parent node. And when the next parent attribute is not found, stop the iteration. The following puts the logic in the __iter__ method of the class, which is now a generator function:

class Tree:
    def __init__(self, parent=None, value=0):
        self.value = value
        self.parent = parent

    def __iter__(self): 
        _parent = self.parent
        yield self.value
        while True:
            try:               
                yield _parent.value 
                _parent = _parent.parent
            except AttributeError:
                break  

    def sum_from_node(self):
        list_ = [item for item in self]
        print list_
        return sum(list_)

Demo:

parent = Tree()
child = Tree(parent=parent, value=8)
child2 = Tree(parent=child,value=10)
child3 = Tree(parent=child2,value=4)
print child3.sum_from_node()
# [4, 10, 8, 0]
# 22

How to iterate through instances in a tree?

2 Answers2