CODEWITHSUNDEEP
pythonbinary-treeparentexpression-trees
MikeHD
MikeHD

Reputation: 1

Adding parent pointer to each node when creating binary expression tree

So I have a perfectly working binary expression tree, but when I tried to modify it to add a parent pointer to each node, (which I will later need to create a path from a node to the root), it doesn't work.

class Node:
    def __init__(self, value, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent


class Tree:
    def __init__(self, lst):
        self.it = iter(lst)  # Create an iterator over the list
        self.lst = lst
        self.root = None

    def create_tree(self):  # Helper function
        value = next(self.it, None)
        print(value)
        N = Node(value)
        if self.root is None:
            self.root = N
        if value is None:  # No more value
            return None
        if not value.isdigit():  # N = Parent
            NL = self.create_tree()  # Use recursion to build the left subtree
            NR = self.create_tree()  # Use recursion to build the right subtree
            return Node(value, NL, NR, parent=N)  # create a Node instance with them as children

        else:  # We need a leaf node
            return Node(value, parent=N)

lst = ["+", "*", "2", "6", "/", "10", "2"]
t = Tree(lst)
t.create_tree()

Now the error is here in these lines I think: N = Node(value) return Node(value, NL, NR, parent=N) return Node(value, parent=N) Parent=N is the same value as the variable "value" which I call the instance on. What can I replace instead of N to call as the parent for this value?

Upvotes: 0

Views: 543

Answers (1)

trincot
trincot

Reputation: 350766

The problem is here:

return Node(value, NL, NR, parent=N)

and here:

return Node(value, parent=N)

It is not true that this new node's parent will be N. N was created as Node(value), and here we are creating another node for the same value, yet have its parent refer to the other, duplicate node.

It is easier when you don't pass a parent argument to the Node constructor, but have the node constructor set that attribute to None.

To establish the parent links, you can let the constructor assign to the parent attribute of its children. So if a left argument is given, let that left get a parent reference to the currently initialised instance (self).

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        if self.left:
            self.left.parent = self
        self.right = right
        if right:
            right.parent = self
        self.parent = None


class Tree:
    def __init__(self, lst):
        it = iter(lst) # Create an iterator over the list
        
        def create_tree():  # Helper function
            value = next(it, None)
            if value is None:  # No more value
                return None
            if value.isdigit():  # We need a leaf node
                return Node(value)
            # Use recursion to build the left and right subtree and
            #     create a Node instance with them as children
            return Node(value, create_tree(), create_tree())

        self.root = create_tree()


lst = ["+", "*", "2", "6", "/", "10", "2"]
t = Tree(lst)

Other remarks

It is not good practice to do this:

    self.lst = lst

The tree should not keep a reference to the list that the caller had provided. This means that list cannot be garbage collected even though those values have already been processed and stored as nodes in the tree.

Secondly, create_tree is a helper function and should not be made available to the the user of your class as a method. The caller has passed the list of values to the constructor and should expect the constructor to have constructed the tree with those values. It is counter-intuitive that even though the constructor was called, the tree still needs to be ... constructed with a call to create_tree().

Upvotes: 1

Related Questions