Implementing Euler Tour in Python

Question

I am trying to implement the following Euler Tour in Python.

However, I am stuck on storing the top values. My code implementation is:

def rmq(root, level, prev=None):
    if not root:
        return True
    euler.append(root.data)
    levels.append(level)  
    ret = rmq(root.left, level+1, (root.data, level))
    ret = rmq(root.right, level+1, (root.data, level))  
    if not (root.left or root.right):
        euler.append(prev[0])
        levels.append(prev[1])
        return True
    if ret:
        euler.append(root.data)
        levels.append(level)


levels = []
euler = []
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.right.left = Node(8)
root.left.right.right = Node(9)

rmq(root, 0)
print(euler)
print(levels)

And the output I am getting from the above code, for the lists Euler and is:

[1, 2, 4, 2, 5, 8, 5, 9, 5, 5, 3, 6, 3, 7, 3, 3]

[0, 1, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 1, 2, 1, 1]

The end goal is to implement this but in a simpler way.

Please help me reach the end goal.

@mkrieger1 I require the output to be the same as that in the image, but my code does not trace back to the previous node as can be seen in my output. I would appreciate any help to solve the problem. — Tanmay, Nov 23 '20 at 22:09

QuadU · Accepted Answer · 2020-11-24T00:32:56.097

There is no need to pass current element to your next recursion level. It's easier to handle storing of every elemen'ts values on their own recursion level, like this (I did rewrite the storage of the tree, to avoid having to explicitly calling the left and right elements):

nodeChildren = {
    1: [2, 3],
    2: [4, 5],
    5: [8, 9],
    3: [6, 7]
}

elements = []
levels = []


def traverseNode(node, level=0):
    elements.append(node)
    levels.append(level)
    if node in nodeChildren:
        for child in nodeChildren[node]:
            traverseNode(child, level+1)
            elements.append(node)
            levels.append(level)


traverseNode(1)

print(f"node elements: {elements}")
# output: node elements: [1, 2, 4, 2, 5, 8, 5, 9, 5, 2, 1, 3, 6, 3, 7, 3, 1]

print(f"levels: {levels}")
# output: levels: [0, 1, 2, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 1, 2, 1, 0]

Explanation:

the nodeChildren object is a map: for every node number that has children, a list of children is given. This will work for any kind of tree (note I didn't foresee a mechanism to detect loops - you will get a stack overflow :) in that case)
traversnode will add it's number and level to the respective lists
it will check whether the cuurent node has any children. If so, it will recursively traverse these children and re-append itself to the lists of numbers and levels.

Implementing Euler Tour in Python

1 Answers1