Binary expression trees - Printable Version

Binary expression trees - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: Binary expression trees (/thread-30441.html)

Binary expression trees - CristinaSpanoche - Oct-21-2020

Hi,

I am trying to build a decision tree from the prefix. The prefix is given in a string, I am reading it by identifying operators and operands from it. No issues here.
My trouble is with actually building the tree, but not using a stack.
Here is my code for adding nodes to the tree:

    def add(self, value):        
        if self.root is None:
            self.root = BinaryTreeNode(value)
        else:
            ptr = self.root
        while True:
            if ptr.value in ["+", "-", "*", "/", "%", "//", "**"]:
                if ptr.left is None:
                    ptr.left = BinaryTreeNode(value)
                    break
                else:
                    ptr = ptr.left
            else:
                if ptr.right is None:
                    ptr.right = BinaryTreeNode(value)
                    break
                else:
                    ptr = ptr.right

The problem is it is not moving on the right branch of the tree. Example: "+ * 2 3 - 20 / 15 3"
The code above is actually building 3 as a the right side of the 2 node, instead of both being the left & right of the "*" node.
So smth like this:

Output:     +
   *
 2
    3

instead of:

Output:      +
   *
 2   3

So the error is that the code doesn't move back up on the branch of the tree.
Any idea how to solve this?

Many thanks!
Cristina

RE: Binary expression trees - bowlofred - Oct-23-2020

Look at your logic as you walk down the tree:

Am I on an operator?
If so, is the left side empty? (If it is, set the value on the left)
If left side is not empty, make left side the new pointer

At the moment, nothing in the "it is an operator" conditional will examine or redirect to the right. That only happens in the non-operator block.

I'm not sure what logic you're using to create the tree, but you probably need another conditional in there to see if you want to add on the right.