Search code examples
pythonarraysbinary-search-tree

How can I convert an array of integers into a BST? - in particular how can I initialise the BST, then add nodes to this root?


I am given an array of integers and I would like to convert into a BST;

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

    def insert(self, value):
        if value<self.value: 
            if not self.left: 
                self.left = BST(value)   
            else: 
                self.left.insert(value)   
        else: 
            if not self.right: 
                self.right = BST(value)  
            else: 
                self.right.insert(value)
        return self

array = [3,10,5,2,7,6,11] 

def insertArrayEntryIntoBst(array): 
    currentNode = BST()
    for i in range(len(array)):  
        currentNode.insert(array[i])

Challenges that I have:

  1. How do I initialise the BST? - in the insert() function do I need to start with a line that reads if not currentNode: BST(array[0])?

  2. After initialising, is my code correct for insertArrayEntryIntoBst()? The idea is simply to loop through the input array and let the insert() function do its magic.

  3. Do I need a value argument in this case? - since the integer value in the array will represent both the node and its value? (which will always be the same thing)


Solution

    1. You may construct first node outside loop with the first item of the array.

    2. If you need to access the node. So it can be returned as well.

    class BST: 
        def __init__(self,value): 
            self.right = None
            self.left = None
            self.value = value
    
        def insert(self, value):
            if value<self.value: 
                if not self.left: 
                    self.left = BST(value)   
                else: 
                    self.left.insert(value)   
            else: 
                if not self.right: 
                    self.right = BST(value)  
                else: 
                    self.right.insert(value)
            return self
    
    def insertArrayEntryIntoBst(array):
        currentNode = BST(array[0])
        for i in range(1,len(array)): 
          currentNode.insert(array[i])
        return(currentNode)
    
    array = [3,10,5,2,7,6,11] 
    
    myNode=insertArrayEntryIntoBst(array)
    print(myNode.value);
    print(myNode.left.value);
    print(myNode.right.value);