Strange behavior in Python code

Question

I am trying to write a simple method to link the nodes of a tree together in this way:

Every leaf is linked to the previous and the next leaf in the tree
Every non-leaf is linked to the previous and the next leaf in the tree

For example, if we have this tree:

    A
  / |  \
 B  C    D
   / \  / \
  E  F  G  H
        |
        I

This should be the result of the method:

B.nextToken = E
C.prevToken = B
E.nextToken = F
E.prevToken = B
F.nextToken = I
C.nextToken = I
H.prevToken = I

Here is the method code:

prevToken = None
def depthFirstTraverseTokenLinking(tree):
    global prevToken
    if len(tree.children) == 0:
        tree.prevToken = prevToken
        if prevToken != None :
            prevToken.nextToken = tree # Is something wrong with this line?
        prevToken = tree
        return

    for c in tree.children:
        depthFirstTraverseTokenLinking(c)

    tree.prevToken = tree.children[0].prevToken
    tree.nextToken = tree.children[-1].nextToken

For some strange reason, the non-leaves aren't linked to the next leaves, for example:

C.nextToken = None

Although

F.nextToken = I

I wonder why is that happening? The last lines at the end of the recursive function should grantee that a parent will have the same next as its last child!

Is there a reason you're not implementing a stack for backtracking? — Joel Cornett
– Joel Cornett, Commented Feb 14, 2013 at 7:15
Why would you use a global here? Why not just have a kwarg depthFirstTraverseTokenLinking(tree, prevToken=None)? — Demian Brecht
– Demian Brecht, Commented Feb 14, 2013 at 7:26

shinjin · Accepted Answer · 2013-02-14 07:38:54Z

1

The problem is, when you visit C, you traverse only it's children E & F.

"I" hasn't been visited yet, so C.children[-1].nextToken == None because only visiting "I" will set F.nextToken

Solution: you'll have to do a run on all leaves first, then a second run on the internal nodes.

For example:

prevToken = None
def depthFirstTraverseTokenLinking(tree):
    depthFirstTraverseTokenLinkingPhase1(tree)
    depthFirstTraverseTokenLinkingPhase2(tree)

def depthFirstTraverseTokenLinkingPhase1(tree):
    global prevToken
    if len(tree.children) == 0:
        tree.prevToken = prevToken
        if prevToken != None :
            prevToken.nextToken = tree # Is something wrong with this line?
        prevToken = tree
        return

    for c in tree.children:
        depthFirstTraverseTokenLinkingPhase1(c)

def depthFirstTraverseTokenLinkingPhase2(tree):
    if len(tree.children) == 0:
        return

    for c in tree.children:
        depthFirstTraverseTokenLinkingPhase2(c)

    if tree.children[0].prevToken is not None:
        tree.prevToken = tree.children[0].prevToken
    else:
        tree.prevToken = tree.children[0]

    if tree.children[-1].nextToken is not None:
        tree.nextToken = tree.children[-1].nextToken
    else:
        tree.nextToken = tree.children[-1]

Also note the change for the prevToken/nextToken of internal nodes. This is needed if you want them to link to the actual first/last leaf.

edited Feb 14, 2013 at 7:38

answered Feb 14, 2013 at 7:29

shinjin

3,0577 gold badges33 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Betamoo Over a year ago

Do you think there is another solution other than 2 runs?

Sharp3 · Accepted Answer · 2013-02-14 08:51:53Z

Alternatively, use generators an an instance-checking loop

The generator yields the node as the base case if the node has no children, else another generator to travel down the tree. Caveat here is that node.children is ordered from left to right.

def leafs(node):
    if len(node.children) == 0:
        yield node
    else:
        for child in node.children:
            yield leafs(child)

...and a loop with stack of generators... This got uglier as I wrote it - I think you could clean it up a bit and get rid of the while True...

current_node = leafs(a)
stack = []
last_node = None
while True:
    if isinstance(current_node, types.GeneratorType):
        stack.append(current_node)
        current_node = current_node.next()
    else:
        if last_node and last_node != current_node:
            last_node.nextToken = current_node
            current_node.prevToken = last_node
            last_node = current_node
        try:
            current_node = stack[-1].next()
        except StopIteration:
            stack.pop()
        except IndexError:
            break

Collectives™ on Stack Overflow

Strange behavior in Python code

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related