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?
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 Node
s to be used outside of the Tree
class (if possible).
To traverse the tree bottom up, here are two methods you can try:
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP