In place transform tree in python

Question

1. What is the best practice for traversing a tree and modifying it in-place?

This is what I have so far:

class N: # Node
    def __init__(self, name, *children):
        self.name = name
        self.children=children

    def __iter__(self):
        yield from ((yield from c) for c in self.children)
        yield self

    def __repr__(self):
        return self.name + '(' + ', '.join(str(c) for c in self.children) + ')'

t = N('parent', N('a', N('b')), N('c', N('d')), N('E', N('f'), N('g', N('h')), N('I', N('j'))), N('k', N('l')))

print(t)

for n in t:
    if n==None:
        continue
    print(n)
    if n.name == "E":
        print('How do I replace this node?')
        n = N('new', *n.children)  # obviously doesn't work

print(t)# now 'E' node should be 'new' node

Of course I can change a node through the parent node, but that makes the code less elegant, because I then need an extra loop:

for n in tree:
    for place, child in enumerate(n.children):
        if child.name=='E': # typo: was n.children
            n.children[place] = N('new', *child.children)

2. Also, is there a way of abstracting out the traversal order? I would like to do something like this for any tree that implements __iter__:

for n in depth_first(tree): or for n in level_order(tree):

3. Is there a universal way to restart with a node if it was changed?

   for n in level_order_redo(tree): pass #if node changed, automatically restart with modified node

Application is a term rewriting system.

Answer 1

For starters (probably just a typo): in your suggested solution, the line n.children[place] = N('new', *n.children) should be n.children[place] = N('new', *child.children). Now to your questions:

1. Yes and No

It depends very much on the implementation of the tree. While you could add more internal structure to your node class (e.g. reference to parent and index) or implement some kind of convenience iterator like

def pc_iter(self):  # df pre-order parent-child-index iterator
    agenda = [self]
    while agenda:
        n = agenda.pop()
        if n.children:
            for i, c in reversed(list(enumerate(n.children))):
                yield (n, c, i)   # important to yield before appending
                agenda.append(c)  # for changes during iteration
        else:
            yield (n, None, None)

which would allow you to shorten the in-place replacement loop

for n, child, i in t.pc_iter():
    if child and child.name == 'E':
        n.children[i] = N('new', *child.children)

I would hardly consider this less clunky then the solution you already have.

2. No (even though in your case, yes)

Even if every tree implements the same order type in their __iter__() (such as post-order in your case), none of these orders (pre-order, in-order, post-order, level-order) define a unique tree. In other words, for any node-sequence (len > 2), there exist multiple possible trees (each of which differ in their other orders), e.g.:

# trees
a[b, c, d]
a[b[c], d]
# have identical pre-order traversal:
(a, b, c, d)
# but different level-order traversal: 
(a, b, c, d) vs. (a, b, d, c)
# and different post-order traversal: 
(b, c, d, a) vs. (c, b, d, a)

All of that is, of course, assuming that the traversal only yields the nodes' payload (name in your case), and not the nodes themselves (as your __iter__() does which is unusual behaviour for any kind of collection data-type). In the latter case, the first (or last - depending on the order) node returned is the root node and holds all the information you need to construct the other traversals.

3. Not really (and why would you want to)

As can be seen above, the changing of a node during iteration (which I would go as far to call an anti-pattern) was only possible because your were actually iterating over the nodes and not the payload. Additionally, you were not replacing the node when the iterator had reached that node, but when it was at that node's parent.

That being said -- and assuming that your level-order(tree) knows about the tree's internal structure and actually yields nodes and not payload -- the function could maintain a queue (which is usually used there) of parent-child-index tuples, and after yielding parent, check the equality of child and parent's index-th child, and clear the queue in case of a change.

4.

If you want to change Node 'E' to 'new' during iteration, why don't you just do:

for n in tree:
    if n.name == 'E':
        n.name = 'new'

That would save you a lot of hassle and, judging from how you called your node constructor, you have no other reference to the 'E' node that you would inadvertently alter in the process.