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.
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: