bst.py

# Need to work on this!
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    #prints our BST in string format
    def __str__(self):
        return binaryTreeToStr(self.root)

    #return true if value exists in BST
    def getIterative(self, val):
        cur = self.root
        while(cur):
            if cur.val == val:
                return True
            elif cur.val > val:
                cur = cur.left
            else:
                cur = cur.right
       return False     

    def getRecursive(self, val):
        return self._getRecursive(val, self.root)

    def _getRecursive(self, val, curNode):
        if not curNode:
            return False
        if curNode.val == val:
            return True
        elif curNode.val > val:
            return _getRecursive(val, curNode.left)
        else:
            return _getRecursive(val, curNode.right)
            
    
    def insertIterative(self, val):
        if not self.root:
            self.root = Node(val)
        else:
            cur = self.root
            while(cur):
                prev = cur
                if cur.val > val:
                    isLeft = True
                    cur = cur.left
                else:
                    isLeft = False
                    cur = cur.right
            if isLeft:
                prev.left = Node(val)
            else:
                prev.right = Node(val)

    def insertRecursive(self, val):
        self.root = self._insertRecursive(val, self.root)
        
    def _insertRecursive(self, val, curNode):
        if not curNode:
            return Node(val)
        if curNode.val > val:
            curNode.left = self._insertRecursive(val, curNode.left)
        else:
            curNode.right = self._insertRecursive(val, curNode.right)
        return curNode
        
        
    def deleteRecursive(self, val):
        self.root = self._deleteRecursive(val, self.root)
        
    def _deleteRecursive(self, val, curNode):
        if curNode is None:
            return None
            
        if curNode.val < val:
            curNode.right = self._deleteRecursive(val, curNode.right)
        
        elif curNode.val > val:
            curNode.left = self._deleteRecursive(val, curNode.left)
            
        else:
            # case 1 has no children
            if not curNode.left and not curNode.right:
                return None
            # case 2 has 2 children
            elif curNode.left and curNode.right:
                # find smallest element in right subtree
                smallest = self.getSmallest(curNode.right)
                # delte smallest element
                curNode.right = self._deleteRecursive(smallest.val, curNode.right)
                
                #now replace curNode with smallest
                smallest.left = curNode.left
                smallest.right = curNode.right
                return smallest
             else:
                if curNode.left:
                    return curNode.left
                else:
                    return curNode.right

        return curNode
    def getSmallest(self, curNode):
        while(curNode.left):
            curNode = curNode.left
        return curNode