Memoizing a tree's parent pointers in Python

Question

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?

• RootTwo: Does the Tree class have methods for modifying the tree? For example, adding or deleting nodes, etc.? They would need to update self.memo so that is stays synched with the state of the tree.

Answer 1

Nodes are usually used internally within the tree and are created inside the insert function of your tree. This is to hide the implementation for users as well as prevent any corruptions that could occur due to external mutability. This isn't Python specific, but more about data structures in general. Data is encapsulated in the structure and use specific operations (functions) for retrieval/mutations.

I'm not sure what your use case is here, but I'd deter you from allowing Nodes to be used outside of the Tree class (if possible).

To traverse the tree bottom up, here are two methods you can try:

1. Reverse level order traversal

2. implement the binary tree with a list internally. Then if you wanted to traverse from the bottom up, the last item in the list would certainly be the node at the bottom of the tree and you can get its parent via a list index (you can work this out by reading the previous link).