Create a binary search tree in python with the support of variables

[FallArk]

My instructor asked us to create a binary search tree in python that supports variables. i.e. the tree will have variables inside, and the user can get the values for those variables by looking for the name of that variable. I don't really know how to implement this.
What I have so far:

class VarTree:
    class Node:
        __slots__ = "_value", "_left", "_right", "_var"
        def __init__(self, l, val, r, v):
            self._left = l;
            self._value = val;
            self._right = r;
            self._var = v;
    def __init__(self):
        self._root = None
    def is_empty(self):
        if self._root is None:
            return True
        else:
            return False
    def _insert(self, here, var, value): #insert a variable with value, if the var already exists, replace with the new value
        if here is None:
            return self.Node(None, value, None, var)
        elif var < here._var:
            return self.Node(self._insert(here._left, var, value), here._value, here._right, here._var)
        elif var == here._var:
            return self.Node(here._left, value, here._right, here._var)
        elif var > here._var:
            return self.Node(here._left, here._value, self._insert(here._right, var, value), here._var)
        else:
            return here
    def _search(self, here, var): #find the variable and return the node
        if var > here._var:
            return self.Node(here._left, here, self._search(here._right, var), )
        elif var < here._var:
            return self.Node(self._search(here._left, var), here, here._right)
        else:
            return here
    def assign(var, value): #Should "self" be included in the parameters 
        return None #Should I call _insert
    def lookup(var):
        return None #Should I call _search

One hint was given to us:

strings can be compared

I know from the hint that instead of comparing values when inserting or searching, i should use variable names instead. But it is really confusing.
some of the exact requirements:

Defining a Binary Tree
There is no need for any self-balancing features in this assignment -- just the a simple binary tree supporting the ability to store new variables, to associate values with those variables, and to retrieve the value of a variable.

For consistency, call your file vartree.py

Required Features in Implementation
Nested Node class definition for binary tree node
with __slots__ to save list memory
and __init__ a constructor
__init__() a constructor for an empty tree
_search(here, var) recursively search tree rooted 'here' for variable 'var'
returning correct Node, or None if not found
_insert(here, var, value) return a search tree with variable inserted or updated
this should be a recursive implementation for immutable behavior
assign(var, value) public method to assign to a variable
lookup(var) public method retrieve value of variableif the variable does not yet exist, assign it zero
Good functions for Completeness / Practice
is_empty() Identify whether tree is empty
__len__() returns number of elements in list
__iter__() inorder iterator generator(with yield statements)
__str__() represents entire tree as a string
For full credit, this must be no worse than log-linear time and not quadratic

This VarTree will be used to look up variable values, so when an infix expression like :

x = y = 4

can be turned into postfix :

xy4==

, this tree will bring up and store the correct values.

 

[alyafey22]

What exactly is the problem you are facing ? Let is start with the insert method. Is it working correctly ?

 

[FallArk]

What exactly is the problem you are facing ? Let is start with the insert method. Is it working correctly ?

No, it does not. It runs but no insertion was made

 

[alyafey22]

In your implementation of the insert method, you are returning a node. Shouldn't you update the tree ?

 

[FallArk]

In your implementation of the insert method, you are returning a node. Shouldn't you update the tree ?

Thanks, My updated version(probably still needs a lot of work):

class VarTree:
    class Node:
        __slots__ = "_value", "_left", "_right", "_var"
        def __init__(self, l, r, val, var):
            self._left = l;
            self._value = val;
            self._right = r;
            self._var = var;
    def __init__(self):
        self._root = None
    def is_empty(self):
        if self._root is None:
            return True
        else:
            return False
    def _insert(self, here, var, value): 
        if self._root is None:
            self._root = self.Node(None, None, value, var)
        elif var < here._var:
            here._left = self._insert(here._left, var, value)
            return here
        elif var == here._var:
            return here
        elif var > here._var:
            here._right = self._insert(here._right, var, value)
            return here
        else:
            return here
    def _search(self, here, var):
        if var is None:
            return None
        elif var > here._var:
            return self._search(here._right, var)
        elif var < here._var:
            return self._search(here._left, var)
        elif var == here._var:
            return here
        else:
            return here
    
    def assign(self, var, value):
        current = self._search(self._root, var)
        if current is None:
            self._insert(self._root, var, value)
        else:
            current._value = value
    def lookup(self, var):
        current = self._search(self._root, var)
        if current is None:
            self._insert(self._root, var, 0)
        else:
            return current._value

 

[alyafey22]

You are close. what about the case when you have a non-empty tree and you want to insert a non-existent variable? The node of that variable must be inserted as a leaf node but you don't have a base case for that.

 

[FallArk]

You are close. what about the case when you have a non-empty tree and you want to insert a non-existent variable? The node of that variable must be inserted as a leaf node but you don't have a base case for that.

I'm thinking that the assign function will take care of that, and then my _insert function will have an if inside the elifs, where if the variable is smaller than the current variable, and the left is none, it will be inserted. if the left of current has a variable, compare those two again, until it find a place

 

[alyafey22]

I'm thinking that the assign function will take care of that, and then my _insert function will have an if inside the elifs, where if the variable is smaller than the current variable, and the left is none, it will be inserted. if the left of current has a variable, compare those two again, until it find a place

Before you search in the here._left and here._right you have to make sure they are not None. If they are just put here._left = Node or here._right = Node , else search the subtree.

 

[FallArk]

Before you search in the here._left and here._right you have to make sure they are not None. If they are just put here._left = Node or here._right = Node , else search the subtree.

I think I did it? Hooray?

class VarTree:
    class Node:
        __slots__ = "_value", "_left", "_right", "_var"
        def __init__(self, l, r, val, var):
            self._left = l;
            self._value = val;
            self._right = r;
            self._var = var;
    def __init__(self):
        self._root = None
    def is_empty(self):
        if self._root is None:
            return True
        else:
            return False
    def _insert(self, here, var, value): 
        if self._root is None:
            self._root = self.Node(None, None, value, var)
            
        elif var < here._var:
            if here._left is None:
                here._left = self.Node(None, None, value, var)
            else:
                here._left = self._insert(here._left, var, value)
            
        elif var == here._var:
            here._value = value
            
        elif var > here._var:
            if here._right is None:
                here._right = self.Node(None, None, value, var)
            else:
                here._right = self._insert(here._right, var, value)
            
        else:
            return here
    def _search(self, here, var):
        if here is None:
            return None
        elif var > here._var:
            return self._search(here._right, var)
        elif var < here._var:
            return self._search(here._left, var)
        elif var == here._var:
            return here
        else:
            return here
    
    def assign(self, var, value):
        self._insert(self._root, var, value)
    def lookup(self, var):
        current = self._search(self._root, var)
        if current is None:
            self._insert(self._root, var, 0)
        else:
            return current._value

 

[alyafey22]

I think I did it? Hooray?

class VarTree:
    class Node:
        __slots__ = "_value", "_left", "_right", "_var"
        def __init__(self, l, r, val, var):
            self._left = l;
            self._value = val;
            self._right = r;
            self._var = var;
    def __init__(self):
        self._root = None
    def is_empty(self):
        if self._root is None:
            return True
        else:
            return False
    def _insert(self, here, var, value): 
        if self._root is None:
            self._root = self.Node(None, None, value, var)
            
        elif var < here._var:
            if here._left is None:
                here._left = self.Node(None, None, value, var)
            else:
                here._left = self._insert(here._left, var, value)
            
        elif var == here._var:
            here._value = value
            
        elif var > here._var:
            if here._right is None:
                here._right = self.Node(None, None, value, var)
            else:
                here._right = self._insert(here._right, var, value)
            
        else:
            return here
    def _search(self, here, var):
        if here is None:
            return None
        elif var > here._var:
            return self._search(here._right, var)
        elif var < here._var:
            return self._search(here._left, var)
        elif var == here._var:
            return here
        else:
            return here
    
    def assign(self, var, value):
        self._insert(self._root, var, value)
    def lookup(self, var):
        current = self._search(self._root, var)
        if current is None:
            self._insert(self._root, var, 0)
        else:
            return current._value

I think it should work but u have an extra else statement that has no effect since the value can be either ><=.

 

[FallArk]

I see. This variable tree is used to help me evaluate an expression in postfix notation with variables. The idea is that the evaluation will take advantage of this tree and a linked list to store values for the variable and values respectively. The instructor's sample code of the actual evaluation looks something like this:

from linkedlist import LinkedList
from vartree import VarTree

def eval_postfix( expr ):
    vals = LinkedList()
    for token in expr:
        if token.isalnum():
            vals.push(token)
        else:
            rval = vals.pop()
            lval = vals.pop()
            vals.push(str(eval(lval + token + rval)))
    return vals.pop()

vars = VarTree()

I know that when encounters a variable, this function should lookup the variable and use that value for computation, if the expression is something like :"xyz4==", then it will assign values for those variables, I can't quite figure out how to implement this method.

 

[alyafey22]

What is unclear about the pseudocode ?

 

[FallArk]

What is unclear about the pseudocode ?

My idea is that when a variable is present, I should pop it from the list and then assign the value to it. But in my linked list file, when i use pop, it returns the value of head(use it as a stack). Shouldn't that give me an error? since variable is a string instead of an integer?

from linkedlist import LinkedList
from vartree import VarTree

def eval_postfix( expr ):
    vals = LinkedList()
    for token in expr:
        if token.isalnum():
            vals.push(token)
        elif token == '=':
            vval = vals.pop() #variable value 
            vari = vals.pop() #variable name
            vars.assign(vari, vval)
            vals.push(vars.lookup(vari))
        else:
            rval = vals.pop()
            lval = vals.pop()
            vals.push(str(eval(lval + token + rval)))
    return vals.pop()

vars = VarTree()

Made a few changes, and it works for the most part, but when i test out b = 6 first, it outputs correctly with 6, but when i test b * 6 afterwards, an error occurred instead of output 36

 

[FallArk]

After realizing how linkedlist works, I figured out why the first time it isn't working properly. If a string is put inside the list, i use pop to retrieve it, a string will be returned. So all I have to do is make sure my previous files does this correctly. So, here is my final solution:

from linkedlist import LinkedList
from vartree import VarTree

vars = VarTree()

def eval_postfix( expr ):
    vals = LinkedList()
    for token in expr:
        if token.isalnum():
            vals.push(token)
        elif token == '=':
            vval = vals.pop() #variable value 
            vari = vals.pop() #variable name
            vars.assign(vari, vval)
            vals.push(vars.lookup(vari))
        else:
            rval = vals.pop()
            lval = vals.pop()
            if lval[0].isalpha(): #is lval is a variable, lookup that value inside the tree and give it to lval
                lval = vars.lookup(lval)
            vals.push(str(eval(lval + token + rval)))
    return vals.pop()

I have tested a few cases and they all worked.