How do i fix this "convert list to BST" problem?

Question

why isn't my Tree object retaining the values i pass it? It always keeps on printing None each time i run the script.

class:

class Tree:
    def __init__(self,key=None):
        self.left,self.right = None,None
        self.key = key

    def insert(key):
        return Tree(key)

    def convert(self,list):
        if len(list) > 1:
            mid = len(list)//2
            self = Tree.insert(list[mid]) 
            self.left = Tree.convert(self,list[:mid])
            self.right = Tree.convert(self,list[mid+1:])
        else:
            try:
                self = Tree.insert(list[0])
            except:
                self = None

        return self

Input:

int_list = [1,2,3]

Main:

tree = Tree()
tree.convert(int_list)

print(tree.key)
print(tree.left.key)
print(tree.right.key)

Expected Output

2
1
3

Output Received

None

can there be a way to fix this issue while keeping the convert() as a method of the class Tree.

Answer 1

The problem is that your convert method doesn't do anything with the current value of self, but overwrites it. The main program calls the method on tree (which is self in the function), but as self is discarded and another value is assigned to this local name, the main's tree remains unaltered.

It is also apparent that you recursively call convert as a static method, directly on Tree. This is actually going in the right direction, but you should also do it in your main program, and then declare the convert method as a static method -- without a self parameter. The main program should use the tree node that this method returns.

Here is the version with minimal corrections, with comments indicating where changes were made:

class Tree:
    def __init__(self, key=None):
        self.left,self.right = None,None
        self.key = key

    def insert(key):
        return Tree(key)

    # Define as static, without a self parameter
    @staticmethod
    def convert(list):
        if len(list) > 1:
            mid = len(list)//2  
            self = Tree.insert(list[mid]) 
            # As convert is now static, don't pass self argument
            self.left = Tree.convert(list[:mid])
            self.right = Tree.convert(list[mid+1:])
        else:
            try:
                self = Tree.insert(list[0])
            except:
                self = None

        return self

int_list = [1,2,3]

# Don't call the Tree constructor, 
# but get the root from calling `convert` as a static method
tree = Tree.convert(int_list)

print(tree.key)  # 2
print(tree.left.key)  # 1
print(tree.right.key)  # 3

This works, but still has some things that need to be improved:

• It is better practice to not use the name self when it is not an instance method (as is now the case here). You could name it root.
• Your code will be shorter (without that try) when you use as base case the case where the list is empty (instead of having 1 element).
• Don't use list as name -- it is already used for the native list type.
• The method insert is so basic that it doesn't really give any advantage. It is actually shorter code to call Tree than Tree.insert. So just drop that insert method.
• The Tree constructor should not have a default value for key. It is bad practice to create a root node that has no value. An empty tree has no nodes, not one. So remove that =None part.
• You can assign None to both left and right by chaining =.

So we get this:

class Tree:
    def __init__(self, key):  # No default for key.
        self.left = self.right = None  # chain assignment
        self.key = key

    # No need for insert method

    # Define as static, without a self parameter
    @staticmethod
    def convert(values):  # Don't use list as name
        if values:
            mid = len(values)//2
            root = Tree(values[mid])  # Call constructor directly
            root.left = Tree.convert(values[:mid])  # No self argument
            root.right = Tree.convert(values[mid+1:])
            return root

int_list = [1,2,3]

# Don't call the Tree constructor, 
# but get the root from calling `convert` as a static method
tree = Tree.convert(int_list)

print(tree.key)  # 2
print(tree.left.key)  # 1
print(tree.right.key)  # 3