Question

1. Delete function for a BST class given a value. You need to make sure that the tree remains a binary search tree after deletion. Your function should work for nodes that can handle all the following cases:

a. Node to be deleted has no children

b. Node to be deleted has only one child

c. Node to be deleted has two children

2. A BST class function that returns the maximum value in a tree.

3. A BST class function that is given value, it calculates the sum of all values in the tree lower than this value.

4. A BST class function that counts the number of nodes in a tree. This function has only the self parameter and return the number of nodes.

All functions implemented need to be part of a binary search tree class and not functions on their own. Hence, you should be using the self parameter in all of these functions.

Need to use PYTHON 3!! Thanks!!

Example of BST class:

class BST:

class TreeNode:

def __init__(self, val):

self.left = left

self.right = right

self.value=value

def __init__(self):

self.root = None

Answer 1

#have made it the menu driven if you encounter any problem let me know in #comment the link for the code in below, 

#Code Link => https://repl.it/@FAYAZPASHA/Python-3-7


class Node(object):
    allSum = 0
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

    def insert(self, data):
        ''' For inserting the data in the Tree '''
        if self.data == data:
            return False        # As BST cannot contain duplicate data

        elif data < self.data:
            ''' Data less than the root data is placed to the left of the root '''
            if self.leftChild:
                return self.leftChild.insert(data)
            else:
                self.leftChild = Node(data)
                return True

        else:
            ''' Data greater than the root data is placed to the right of the root '''
            if self.rightChild:
                return self.rightChild.insert(data)
            else:
                self.rightChild = Node(data)
                return True

    def minValueNode(self, node):
        current = node

        # loop down to find the leftmost leaf
        while(current.leftChild is not None):
            current = current.leftChild

        return current

    def maxValueNode(self, node):
        current = node
        # loop down to find the leftmost leaf
        while (current.rightChild is not None):
            current = current.rightChild
        return current

    def delete(self, data):
        ''' For deleting the node '''
        if self.find(data) == False:
            print("NO node found")
            return
        if self is None:
            return None

        # if current node's data is less than that of root node, then only search in left subtree else right subtree
        if data < self.data:
            self.leftChild = self.leftChild.delete(data)
        elif data > self.data:
            self.rightChild = self.rightChild.delete(data)
        else:
            # deleting node with one child
            if self.leftChild is None:
                temp = self.rightChild
                self = None
                return temp
            elif self.rightChild is None:
                temp = self.leftChild
                self = None
                return temp

            # deleting node with two children
            # first get the inorder successor
            temp = self.minValueNode(self.rightChild)
            self.data = temp.data
            self.rightChild = self.rightChild.delete(temp.data)

        return self


    def allNodeSum(self, node, data):
        if node != None:
            # print(node.data, data)
            temp = node.data
            if node.data >= data:
                temp = 0
            return temp + self.allNodeSum(node.leftChild, data) + self.allNodeSum(node.rightChild, data)
        return 0


    def inorder(self):
        ''' For Inorder traversal of the BST '''
        if self:
            if self.leftChild:
                self.leftChild.inorder()
            print(str(self.data), end = ' ')
            if self.rightChild:
                self.rightChild.inorder()

    def find(self, data):
        ''' This function checks whether the specified data is in tree or not '''
        if (data == self.data):
            return True
        elif (data < self.data):
            if self.leftChild:
                return self.leftChild.find(data)
            else:
                return False
        else:
            if self.rightChild:
                return self.rightChild.find(data)
            else:
                return False

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

    def insert(self, data):
        self.sz += 1
        if self.root:
            return self.root.insert(data)
        else:
            self.root = Node(data)
            return True

    def delete(self, data):
        if self.find(data):
            self.sz -= 1
        if self.root is not None:
            return self.root.delete(data)

    def maximumValue(self):
        if self.root:
            return self.root.maxValueNode(self.root).data


    def getSum(self, data):
        if self.root:
            return self.root.allNodeSum(self.root, data)

    def inorder(self):
        print()
        if self.root is not None:
            print('Inorder: ')
            self.root.inorder()

    def getSize(self):
        return self.sz

    def find(self, data):
        if self.root:
            return self.root.find(data)
        else:
            return False

# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    bst = BST()
    while True:
        print("1: Insert new Node")
        print("2: Delete Node")
        print("3: Maximum Value in a Tree")
        print("4: Calculate Sum of Value in the tree lower than Given Value")
        print("5: Number of Nodes in a Tree")
        print("6: To View The tree elements")
        print("0: EXIT")

        print('____________________________')
        n = int(input())
        if n == 1:
            print("Enter the Node value")
            node = int(input())
            bst.insert(node)
        elif n == 2:
            print("Enter the Node to be deleted")
            node = int(input())
            bst.delete(node)
        elif n == 3:
            print(bst.maximumValue())
        elif n == 4:
            print("Enter the Node value to get sum lesser than the given node")
            node = int(input())
            print(bst.getSum(node))
        elif n == 5:
            print(bst.getSize())
        elif n == 6:
            bst.inorder()
            print()
        elif n == 0:
            break