Tree : BinaryTree/BinarySearchTree/Heap

This exercise to implement BT/BST/MinHEAP/MaxHEAP in single program as generalized one by specifying the tree type (BT/BST/MinHEAP/MaxHEAP) and implementation type (LL/A). LL means Linked List and A means Array Implement BinaryTree & Binary search tree using linked list, and Heap using Array.
Hence, Two classes namely Tree_linkedlist and Tree_Array are defined.

Implement the following functions common to binary tree (BT), Binary Search Tree (BST):

 - getRoot()-returns the reference to the root node
 - isLeaf(node)-check whether the given node is leaf node and returns true/false
  - getMin(node)-the called from the main as getMin(getRoot())      
          The functions search and return the minimum value of the tree. 
                  Since the searching in BST is different from BT, the operations for searching for BT and BST are separated by the 
                  checking the treetype (BT/BST)
  - getMin(node)-the called from the main as getMax(getRoot())      
          The functions search and return the maximum value of the tree. 
                   Since the searching in BST is different from BT, the operations for searching for BT and BST are separated by the 
                   checking the treetype (BT/BST)
  - getMedian(node)-the called from the main as getMedian(getRoot())        
            The functions return median for the elements present in the tree. 
                    Since the finding median for BST is different from BT, the operations for finding median for BT and BST are separated 
                     by the checking the treetype (BT/BST)
   - height(node)-the function is called as height(getRoot()) in main. The function returns height of the root node. 
   - Inordertraversal(node) )-the function is called as height(getRoot()) in main
   - Postordertraversal(node) )-the function is called as Postordertraversal (getRoot()) in main
   - Preordertraversal(node) )-the function is called as Preordertraversal (getRoot()) in main

Implement the following functions specific to Binary Tree(BT):

   - InsertRoot(e)-to create the root with e at beginning 
   -  insertintoBT(node,e,child)-create a node with e  and assign as the child of node. Based on the child (l or r), it will be assigned 
                                 as left child and right child. 
   - getNode(node,e)-the function will be called with node initialized with root of the tree. The function starts the search from the root 
                     and continues its search until reaching the node with value as e. if node with e is not present, then return None

Implement the following functions specific to Binary Search Tree(BST):

- insertintoBST(node,e)-the function will be called with node as root.i.e., suitable place to insert e and create the node with e as per 
                        BST properties.  

Implement the following functions specific to MinHEAP/MaxHEAP using array:

-  insertintoHEAP(node,e)-the function will be called with node as root. i.e., heapify will be carried based on type (MinHEAP/MaxHEAP)
                          This function print the elementslist which represents the array of elements of the Heap.

- Inordertraversal(index)-the function will be called as inordertraversal(0) means that inordertraversal starts from the index 0 (index of 
                          root)

Input:

First line – Type of Tree (BT/BST/MinHEAP/MaxHEAP)
For BT/BST Second line:
    Implementation of tree LL/A   (LL – Linked list based implementation. A-Array based implementation)

Then,
    Next line is Number of operations
    Operations are:
    In-Inordertraversal, Pre-Preordertraversal, Post-Postordertraversal
    IR-InsertRoot for BinaryTree (BT)
    I-Insert for BinaryTree(BT)/BST/MinHEAP/MaxHEAP
        I     for insert into BT
        I       for insert into BST
        I       for insert into MinHEAP, MaxHEAP
    Min-get the minimum of BT/BST/ MinHEAP/MaxHEAP
    M-Median
    H-Height        

Sample Input for Binary Tree:

BT
LL      
12
IR 0
I 0 1 l      #insert 1 as left child of 0 
I 0 2 r      #insert 2 as right child of 0
I 1 3 l
I 1 4 r
I 2 5 l
I 2 6 r
In
Post
Pre
Min
H

Sample output for binary Tree

Binary Tree using Linked list is created..
Root is created
0 
1 0             
1 0 2       #inorder traversal output after inserting 2 
3 1 0 2 
3 1 4 0 2 
3 1 4 0 5 2 
3 1 4 0 5 2 6 
3 1 4 0 5 2 6 
3 4 1 5 6 2 0 
0 1 3 4 2 5 6 
0
2

Sample input for Binary Search Tree (BST):

BST
LL
12
I 10   #insert 10
I 20 
I 15
I 45
I 36
I 12
In
Post
Pre
Min   #find the minimum
M      #find the median
H       #height of the tree

Sample output for BST:

Binary Search Tree using Linked list is created..
10 
10 20 
10 15 20 
10 15 20 45 
10 15 20 36 45 
10 12 15 20 36 45 
10 12 15 20 36 45 
12 15 36 45 20 10 
10 20 15 12 45 36 
10          #10  is minimum 
17.5            #17.5 is median
3           #3 is height of the tree    

Sample input for MinHEAP:

MinHEAP
7
I 10
I 20
I 30
I 40
I 5
Min
H

Sample output for MinHEAP:

MinHEAP  Tree using Array is created..
[10]                
[10, 20]            #state of the array maintained by the heap after inserting 20
[10, 20, 30]
[10, 20, 30, 40]
[5, 10, 30, 40, 20]
5            #minimum
2            #height 

###Testcases
Testcase1: testing insertion into BT, inorder traversal 
Testcase2: testing insertion into BT, inorder traversal, preorder, post order traversal
Testcase3: testing insertion into BT, inorder traversal, preorder, post order traversal, minimum
Testcase4: testing insertion into BT, inorder traversal, preorder, post order traversal, minimum, height
Testcase5: testing insertion into BST, inorder traversal 
Testcase6: testing insertion into MinHEAP
Testcase7: testing insertion into MinHEAP, minimum
Code Template

class Tree_LinkedList:
    class Node:
        def __init__(self):
            self.value=None
            self.paraent=None
            self.leftchild=None
            self.rightchild=None


    def __init__(self,typeoftree):
        self.root=None
        self.type=typeoftree #'BT'-BinaryTree
                             #'BST'-BinarySearchTree
        if(self.type=='BT'):
            print("Binary Tree using Linked list is created..")
        if(self.type=='BST'):
            print("Binary Search Tree using Linked list is created..")

    #def constructTree(self):

    def insertintoBST(self,node,e):
            return

    def InsertRoot(self,e):
         return           

    def insertintoBT(self,node,e,child):
        return         

    def delete(self,node):
        return

    def getRoot(self):
        return self.root

    def isLeaf(self,node):
        if(node.leftchild==None and node.rightchild==None):
            return True
        else:
            return False

    #returns the reference of the node which contains the given element
    def getNode(self,node,e):
        return           

    def getMin(self,node):
        if(self.type=='BT'):
            return
        elif(self.type=='BST'):
            return

    def getMax(self,node):
        if(self.type=='BT'):
            return
        elif(self.type=='BST'):
            return

    def getMedian(self,node):
        if(self.type=='BT'):
            return
        elif(self.type=='BST'):
            return

    def height(self,node):
        return

    def depth(self,node):
        return

    def balancedFactor(self,node):
        return

    def  inordertraversal(self,node):
        return

    def  preordertraversal(self,node):
        return

    def  postordertraversal(self,node):
        return




class Tree_Array:
    def __init__(self,typeoftree):
        self.elementslist=[]
        self.type=typeoftree  #type-heap
        self.lastindex=-1
        print(self.type," Tree using Array is created..")

    def constructtree(self,elements):
        return

    def insertintoHEAP(self,e):

        if(self.type=='MinHEAP'):
            return
        if(self.type=='MaxHEAP'):
            return        
        return

    def getRoot(self):
        return

    def getMin(self):
        return 



    def height(self):
        return 0


    def  inordertraversal(self,index):
        return

    def  preordertraversal(self):
        return

    def  postordertraversal(self):
        return



def main():
    tree_type=input()
    if(tree_type=='BT' or tree_type=='BST'):
        tree_imp=input()
        if(tree_imp=='LL'):
            tree=Tree_LinkedList(tree_type)
        elif(tree_imp=='A'):
            tree=Tree_Array(tree_type)
    elif(tree_type=='MinHEAP' or tree_type=='MaxHEAP'):
        tree=Tree_Array(tree_type)


    inputs=int(input())
    while inputs > 0:
         command = input()
         operation = command.split()
         if (operation[0] == "In"):
              tree.inordertraversal(tree.getRoot())
              print("")
         elif (operation[0] == "Pre"):
              tree.preordertraversal(tree.getRoot())
              print("")
         elif (operation[0] == "Post"):
              tree.postordertraversal(tree.getRoot())
              print("")
         elif (operation[0] == "IR"):#For BinaryTree-BT
              node=tree.InsertRoot(operation[1])
              tree.inordertraversal(tree.getRoot())
              print("")
         elif (operation[0] == "I"):
              #print(node.value)
              if(tree_type=='BT'):
                  node=tree.getNode(tree.getRoot(),operation[1])
                  tree.insertintoBT(node,operation[2],operation[3])
                  tree.inordertraversal(tree.getRoot())
                  print("")
              if(tree_type=='BST'):
                  tree.insertintoBST(tree.getRoot(),int(operation[1]))
                  tree.inordertraversal(tree.getRoot())
                  print("")
              if(tree_type=='MinHEAP' or tree_type=='MaxHEAP' ):
                  tree.insertintoHEAP(int(operation[1]))
                  #tree.inordertraversal(0)
         elif (operation[0] == "Del"):
              node=tree.getNode(operation[1])
              if(node!=None):
                  tree.delete(tree.root,node)
         elif (operation[0] == "Min"):

              if(tree_type=='MinHEAP' or tree_type=='MaxHEAP'):
                  print(tree.getMin())
              if(tree_type=='BT' or tree_type=='BST'):
                  print(tree.getMin(tree.getRoot()))
         elif (operation[0] == "M"):
              print(tree.getMedian(tree.getRoot()))
         elif (operation[0] == "H"):
              if(tree_type=='BT' or tree_type=='BST'):
                  print(tree.height(tree.getRoot()))
              if(tree_type=='MinHEAP' or tree_type=='MaxHEAP'):
                  print(tree.height())
        #elif (operation[0] == "CH"):
        #      print(tree.height(tree.getRoot()))

         inputs -= 1

if __name__ == '__main__':
    main()