6
\$\begingroup\$

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?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – RootTwo
    Jul 21, 2020 at 6:46

1 Answer 1

2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.