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.

Answer 1

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.