TransWikia.com

Memoizing a tree's parent pointers in Python

Code Review Asked by Mark Karavan on October 27, 2021

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?

One Answer

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

Answered by chromaticc on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP