#StackBounty: #python #python-3.x #tree Implement BinarySearchTree class in python

Bounty: 50

I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class BinarySearchTree how to make the code more elegant. any review are appreciated.

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


class BinarySearchTree:
    """
    Database strucutre for binary search tree
    1:search
    2:insert
    3:delete
    4:get_height
    5:get_min_value
    6:get_max_value
    """

    def __init__(self, root=None):
        self.root = root

    def __iter(self, cur):
        if cur is not None:
            yield from self.__iter(cur.left)
            yield cur
            yield from self.__iter(cur.right)

    def __repr__(self):
        cur = self.root
        return ''.join(str(i.val) for i in self.__iter(cur))

    def insert(self, key):
        """insert node into binary tree based on node's value"""
        cur = self.root
        if cur is None:
            self.root = TreeNode(key)
            return
        while cur is not None:
            if key < cur.val:
                if cur.left is None:
                    cur.left = TreeNode(key)
                    return
                else:
                    cur = cur.left
            elif key > cur.val:
                if cur.right is None:
                    cur.right = TreeNode(key)
                    return
                else:
                    cur = cur.right

    def search(self, key):
        """find node from binary tree based on node's value"""
        cur = self.root
        if cur is None:
            raise KeyError(f'{key} is not found')
        while cur is not None:
            if key < cur.val:
                cur = cur.left
            elif key > cur.val:
                cur = cur.right
            else:
                return cur

        raise KeyError(f'{key} is not found')

    def get_min_value(self):
        """return the min value from tree"""
        cur = self.root
        while cur is not None and cur.left is not None:
            cur = cur.left
        return cur.val

    def get_max_value(self):
        """return the max value from tree"""
        cur = self.root
        while cur is not None and cur.right is not None:
            cur = cur.right
        return cur.val

    def get_height(self):
        """return tree height of binary search tree"""
        h = 0
        return self.__get_height(self.root, h) if self.root else h

    def __get_height(self, cur, h):
        """recursion the tree with left subtree and right subtree"""
        if cur is None: return h
        left_height = self.__get_height(cur.left, h + 1)
        right_height = self.__get_height(cur.right, h + 1)
        return max(left_height, right_height)

    def delete(self, key):
        """delete the node from binary tree based on node's key value"""
        if self.root is None: raise KeyError('key is not found')
        self.__delete(self.root, key)

    def __delete(self, cur, key):
        """recursion the tree to find the node and delete from tree"""
        if cur is None: return
        if key < cur.val:
            cur.left = self.__delete(cur.left, key)
        elif key > cur.val:
            cur.right = self.__delete(cur.right, key)
        else:
            if cur.left is None:
                return cur.right
            elif cur.right is None:
                return cur.left
            else:
                def __get_successor(n):
                    while n is not None and n.left is not None:
                        n = n.left
                    return n

                successor = __get_successor(cur)
                cur.key = successor.key
                cur.right = self.__delete(cur.right, successor.key)
        return cur


if __name__ == '__main__':
    bst = BinarySearchTree()
    bst.insert(6)
    bst.insert(2)
    bst.insert(8)
    bst.insert(0)
    bst.insert(4)
    bst.insert(7)
    bst.insert(9)
    bst.insert(3)
    bst.insert(5)
    print(bst.search(5).val == 5)
    print(bst.search(0).val == 0)
    print(bst.search(9).val == 9)
    print(bst.search(6).val == 6)
    try:
        bst.search(13)
    except KeyError as e:
        print(e)
    print(bst.get_height() == 4)
    bst.delete(5)
    print(bst.get_height() == 4)
    print(bst.get_max_value() == 9)
    print(bst.get_min_value() == 0)
    bst.delete(3)
    bst.delete(7)
    bst.delete(9)
    print(bst.get_height() == 3)
    print(bst)


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.