CODEWITHSUNDEEP
pythontreedepth-first-search
Betamoo
Betamoo

Reputation: 15860

Strange behavior in Python code

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

For example, if we have this tree:

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

This should be the result of the method:

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:

Although

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!

Upvotes: 0

Views: 129

Answers (2)

Sharp3
Sharp3

Reputation: 108

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

Upvotes: 1

shinjin
shinjin

Reputation: 3027

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.

Upvotes: 1

Related Questions