I have a simple binary tree that has no parent pointers.
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Tree:
def __init__(self, root=None):
self.root = root
I need to traverse the tree from bottom up and cannot modify the Node class, so I'd like to memoize the parents. I can modify the Tree class as such:
class Tree:
def __init__(self, root=None):
self.root = root
self.memo = {}
def memoize(self, node, parent_node):
if node is None:
return False
self.memo[id(node)] = parent_node
self.memoize(node.left, node)
self.memoize(node.right, node)
def get_parent(self, child):
return self.memo[id(child)]
If I create a tree, memoize it, and run get_parent() I see what I expect:
a = Node(1)
tree = Tree(a)
b = Node(2)
c = Node(3)
a.left = b
a.right = c
tree.memoize(a, None) # Tree root is instantiated with no parent
parent = tree.get_parent(b)
print(tree.memo)
>>> {4405793712: None, 4405793856: <__main__.Node instance at 0x1069b13b0>, 4405793928: <__main__.Node instance at 0x1069b13b0>}
print(parent.val)
>>> 1
This seems to work nicely. However, I am a Python beginner, and want to know: is there a more Pythonic way to do this?
self.memoso that is stays synched with the state of the tree. \$\endgroup\$