<jupyter_start><jupyter_text>Binary tree using linked list<jupyter_code>class Tree:
    def __init__(self, value):
        self.value=value
        self.lchild=None
        self.rchild=None
    
    
newBT=Tree("Drinks")
lchild=Tree("hot")
rchild = Tree('Cold')
newBT.lchild=lchild
newBT.rchild=rchild

def preOrder(root):
    if not root:
        return 
    print(root.value)
    preOrder(root.lchild)
    preOrder(root.rchild)
    
def inOrder(root):
    if not root:
        return 
    
    inOrder(root.lchild)
    print(root.value)
    inOrder(root.rchild)
    
def postOrder(root):
    if not root:
        return 
    
    postOrder(root.lchild)
    postOrder(root.rchild)
    print(root.value , end =" ")  
    

preOrder(newBT)
print()
inOrder(newBT)
print()
postOrder(newBT)<jupyter_output>Drinks
hot
Cold

hot
Drinks
Cold

hot Cold Drinks<jupyter_text>Binary tree: Level order traversal and searching<jupyter_code>class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None
    
    def __str__(self):
        return str(self.value)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
class Queue:
    def __init__(self):
        self.linkedList = LinkedList()
    
    def __str__(self):
        values = [str(x) for x in self.linkedList]
        return ' '.join(values)
    
    def enqueue(self, value):
        newNode = Node(value)
        if self.linkedList.head == None:
            self.linkedList.head = newNode
            self.linkedList.tail = newNode
        else:
            self.linkedList.tail.next = newNode
            self.linkedList.tail = newNode
    
    def isEmpty(self):
        if self.linkedList.head == None:
            return True
        else:
            return False
    
    def dequeue(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            tempNode = self.linkedList.head
            if self.linkedList.head == self.linkedList.tail:
                self.linkedList.head = None
                self.linkedList.tail = None
            else:
                self.linkedList.head = self.linkedList.head.next
            return tempNode
    
    def peek(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            return self.linkedList.head
    
    def delete(self):
        self.linkedList.head = None
        self.linkedList.tail = None

        
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

newBT = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Tea")
coffee = TreeNode("Coffee")
leftChild.leftChild = tea
leftChild.rightChild = coffee
rightChild = TreeNode("Cold")
newBT.leftChild = leftChild
newBT.rightChild = rightChild


def levelOrder(rootNode):
    if rootNode is None:
        return None
    else:
        customQueue=Queue()
        customQueue.enqueue(rootNode)
        while not (customQueue.isEmpty()):
            root=customQueue.dequeue()
            print(root.value.data)
            if root.value.leftChild is not None:
                customQueue.enqueue(root.value.leftChild)
                
            if root.value.rightChild is not None:
                customQueue.enqueue(root.value.rightChild)
                
def search(rootNode,element):
         if not rootNode:
                return
         else:
            customQueue=Queue()
            customQueue.enqueue(rootNode)
            while not(customQueue.isEmpty()):
                root=customQueue.dequeue()
                if root.value.data == element:
                    return True
                if root.value.leftChild is not None:
                    customQueue.enqueue(root.value.leftChild)
                
            if root.value.rightChild is not None:
                customQueue.enqueue(root.value.rightChild)
         return False
                
def insert(rootNode, nodeValue):
    if not rootNode:
        rootNode=newNode
    else:
        customQueue=Queue()
        customQueue.enqueue(rootNode)
        while not (customQueue.isEmpty()):
            root=customQueue.dequeue()
            if root.value.leftChild !=None:
                customQueue.enqueue(root.value.leftChild)
            else:
                root.value.leftChild=newNode
                return "Added"
            
            if root.value.rightChild !=None:
                customQueue.enqueue(root.value.rightChild)
            else:
                root.value.rightChild=newNode
                return "Added"

def find_deepest(rootNode):
     if not rootNode:
        return None
     else:
            customQueue=Queue()
            customQueue.enqueue(rootNode)
            while not(customQueue.isEmpty()):
                root=customQueue.dequeue()
                if root.value.leftChild !=None:
                    customQueue.enqueue(root.value.leftChild)
                if root.value.rightChild !=None:
                    customQueue.enqueue(root.value.rightChild)
            deepsetNode=root.value
            return deepsetNode
        
def delete_deepest(rootNode, dnode):
    if not rootNode:
        return None
    else:
         customQueue=Queue()
         customQueue.enqueue(rootNode)
         while(not(customQueue.isEmpty())):
                root=customQueue.dequeue()
                if root.value is dnode:
                    root.value=None
                if root.value.rightChild:
                    if root.value.rightChild is dnode:
                        root.value.rightChild= None
                        return
                    else:
                        customQueue.enqueue(root.value.rightChild)
                    
                if root.value.leftChild:
                    if root.value.leftChild is dnode:
                        root.value.leftChild= None
                        return
                    else:
                        customQueue.enqueue(root.value.leftChild)
                    
def deleteNodeBT(rootNode, node):
    if not rootNode:
        return None
    else:
        customQueue=Queue()
        customQueue.enqueue(rootNode)
        while not(customQueue.isEmpty()):
            root=customQueue.dequeue()
            if root.value.data == node:
                dnode=find_deepest(rootNode)
                root.value.data=dnode.data
                delete_deepest(rootNode,dnode)
                return "DELETED"
            
            if root.value.leftChild is not None:
                    customQueue.enqueue(root.value.leftChild)

            if root.value.rightChild is not None:
                    customQueue.enqueue(root.value.rightChild)
        return "Failed to delete"

def deleteBT(rootNode):
        rootNode.data=None
        rootNode.leftChild=Node
        rootNode.rightChild=None
        print("Deleted entire tree")
        return             
    
newBT = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Tea")
coffee = TreeNode("Coffee")
leftChild.leftChild = tea
leftChild.rightChild = coffee
rightChild = TreeNode("Cold")
newBT.leftChild = leftChild
newBT.rightChild = rightChild
levelOrder(newBT)
print()

newNode=TreeNode("Cola")
print(insert(newBT,newNode))
print()

levelOrder(newBT)
print()

deleteNodeBT(newBT, 'Hot')
levelOrder(newBT)

deleteBT(newBT)<jupyter_output>Drinks
Hot
Cold
Tea
Coffee

Added

Drinks
Hot
Cold
Tea
Coffee
Cola

Drinks
Cola
Cold
Tea
Coffee
Deleted entire tree<jupyter_text>Binary tree with python list<jupyter_code>class BinTree:
    def __init__(self,size):
        self.customList=size *[None]
        self.lastUsedIndex=0
        self.maxSize=size
    
    def insertNode(self,value):
        if self.lastUsedIndex+1==self.maxSize:
            return ("Binary tree is full")
        self.customList[self.lastUsedIndex+1]=value
        self.lastUsedIndex+=1
        return "Added"
    
    def search(self,key):
        for i in range (len(self.customList)):
            if self.customList[i]==key:
                return True
        return False
    
    def preorder(self,index):
        if index >self.lastUsedIndex:
            return
        print(self.customList[index], end= "...> ")
        self.preorder(index*2)
        self.preorder(index*2 +1)   
        
    def inorder(self,index):
        if index >self.lastUsedIndex:
            return
        self.inorder(index*2)
        print(self.customList[index], end= "--> ")
        self.inorder(index*2 +1)           
        
    def postorder(self,index):
        if index >self.lastUsedIndex:
            return
        self.postorder(index*2)
        self.postorder(index*2 +1) 
        print(self.customList[index], end= "=> ")
    
    def levelorder(self,index):
        for i in range(index, self.lastUsedIndex+1):
            print(self.customList[i], end = " ->")
            
    
    #deepest node= index of last used list
    
    def del_elmt(self, key):
        if self.lastUsedIndex==0:
            return None
        
        deepestNode=self.customList[self.lastUsedIndex]
        for  i in range(1, self.lastUsedIndex+1):
            if self.customList[i]==key:
                self.customList[i]=self.customList[self.lastUsedIndex]
                self.customList[self.lastUsedIndex]=None
                self.lastUsedIndex-=1
                return "deleted"
            
    def delBT(self):
        self.customList = None
        return 'Successfully deleted'
    
    
newBt=BinTree(8)
i=0
while i<7:
    newBt.insertNode(i)
    i+=1

print(newBt.search(2))
newBt.preorder(1)
print()
newBt.inorder(1)
print()
newBt.postorder(1)
print()
newBt.levelorder(1)
print(newBt.del_elmt(0))
newBt.levelorder(1)
print(newBt.delBT())<jupyter_output>True
0...> 1...> 3...> 4...> 2...> 5...> 6...> 
3--> 1--> 4--> 0--> 5--> 2--> 6--> 
3=> 4=> 1=> 5=> 6=> 2=> 0=> 
0 ->1 ->2 ->3 ->4 ->5 ->6 ->deleted
6 ->1 ->2 ->3 ->4 ->5 ->Successfully deleted<jupyter_text>Binary search tree<jupyter_code>class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None
    
    def __str__(self):
        return str(self.value)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    

class Queue:
    def __init__(self):
        self.linkedList = LinkedList()
    
    def __str__(self):
        values = [str(x) for x in self.linkedList]
        return ' '.join(values)
    
    def enqueue(self, value):
        newNode = Node(value)
        if self.linkedList.head == None:
            self.linkedList.head = newNode
            self.linkedList.tail = newNode
        else:
            self.linkedList.tail.next = newNode
            self.linkedList.tail = newNode
    
    def isEmpty(self):
        if self.linkedList.head == None:
            return True
        else:
            return False
    
    def dequeue(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            tempNode = self.linkedList.head
            if self.linkedList.head == self.linkedList.tail:
                self.linkedList.head = None
                self.linkedList.tail = None
            else:
                self.linkedList.head = self.linkedList.head.next
            return tempNode
    
    def peek(self):
        if self.isEmpty():
            return "There is not any node in the Queue"
        else:
            return self.linkedList.head
    
    def delete(self):
        self.linkedList.head = None
        self.linkedList.tail = None



class tree:
    def __init__(self,value):
        self.value=value
        self.lchild=None
        self.rchild=None
        
def insert(root,data):     
    if root is None:
        root.value=data
        return 
    
    elif data <= root.value:
        if root.lchild is None:
            root.lchild=tree(data)
        else:
            insert(root.lchild,data)
    else:
        if root.rchild is None:
            root.rchild=tree(data)
        else:
            insert(root.rchild,data)
            
def inserts(root, value):
    if root.value == None:
        root.value= value
    elif value <= root.value:
        if root.lchild is None:
            root.lchild =tree(value)
        else:
            inserts(root.lchild, value)
    else:
        if root.rchild is None:
            root.rchild = tree(value)
        else:
            inserts(root.rchild, value)
    return "The node has been successfully inserted"

def preOrder(root):
    if not root:
        return 
    print(root.value)
    preOrder(root.lchild)
    preOrder(root.rchild)

def inOrder(root):
    if not root:
        return 
    inOrder(root.lchild)
    print(root.value)
    inOrder(root.rchild)

def postOrder(root):
    if not root:
        return 

    postOrder(root.lchild)
    postOrder(root.rchild)
    print(root.value , end =" ")  

def search(root,key):
    if root is None:
        return
    else:
        if root==key:
            return True
        elif root.value:
                if root.lchild.value == key:
                    return True
                else:
                    search(root.lchild,key)
                
        else:
               if root.rchild.value == key:
                    return True
               else:
                    search(root.rchild,key)
        return False

def searchNode(rootNode, nodeValue):
    if rootNode.value == nodeValue:
        return True
    elif nodeValue < rootNode.value:
        if rootNode.lchild.value== nodeValue:
            return True
        else:
            searchNode(rootNode.lchild, nodeValue)
    else:
        if rootNode.rchild.value == nodeValue:
            return True
        else:
            searchNode(rootNode.rchild, nodeValue)    
            
def levelOrderTraversal(rootNode):
    if not rootNode:
        return
    else:
        customQueue = Queue()
        customQueue.enqueue(rootNode)
        while not(customQueue.isEmpty()):
            root = customQueue.dequeue()
            print(root.value.value)
            if root.value.lchild is not None:
                customQueue.enqueue(root.value.lchild)
            if root.value.rchild is not None:
                customQueue.enqueue(root.value.rchild)

            
def minValueNode(bstNode):
    current=bstNode
    while current.lchild is not None:
        current=current.lchild
    return current

def dele(root,value):
    if root is None:
        return
    else:
        if root.value> value:
            root.lchild=dele(root.lchild,value)
        elif value>root.value:
            root.rchild=dele(root.rchild,value)
        else:
            if root.lchild is None:
                    temp=root.rchild
                    root=None
                    return temp
            if root.rchild is None:
                    temp=root.lchild
                    root=None
                    return temp
                
            temp=minValueNode(root.rchild)
            root.value=temp.value
            root.rchild=dele(root.rchild,temp.data)
        return root
def del_BST(root):
        root=None
        root.lchild=None
        root.rchild=None
        print("deleted")
    
BST=tree(None)
inserts(BST,73)
inserts(BST,40)
inserts(BST,50)
preOrder(BST)
print()
inOrder(BST)
print()
postOrder(BST)
#print(searchNode(BST,73))
dele(BST,40)
print()
levelOrderTraversal(BST)<jupyter_output>73
40
50

40
50
73

50 40 73 
73
50<jupyter_text>AVL trees     1. Reduce the time complexity of searching (in skewed tree take O(n) in avl takes(O(log(n))<jupyter_code>class node:
    def __init__(self, num):
        self.value = num
        self.left = None
        self.right = None
        self.height = 1

class AVL:

    def height(self, Node):
        if Node is None:
            return 0
        else:
            return Node.height

    def balance(self, Node):
        if Node is None:
            return 0
        else:
            return self.height(Node.left) - self.height(Node.right)

    def MinimumValueNode(self, Node):
        if Node is None or Node.left is None:
            return Node
        else:
            return self.MinimumValueNode(Node.left)

    def rotateR(self, Node):
        a = Node.left
        b = a.right
        a.right = Node
        Node.left = b
        Node.height = 1 + max(self.height(Node.left), self.height(Node.right))
        a.height = 1 + max(self.height(a.left), self.height(a.right))
        return a

    def rotateL(self, Node):
        a = Node.right
        b = a.left
        a.left = Node
        Node.right = b
        Node.height = 1 + max(self.height(Node.left), self.height(Node.right))
        a.height = 1 + max(self.height(a.left), self.height(a.right))
        return a

    def insert(self, val, root):
        if root is None:
            return node(val)
        elif val <= root.value:
            root.left = self.insert(val, root.left)
        elif val > root.value:
            root.right = self.insert(val, root.right)
        root.height = 1 + max(self.height(root.left), self.height(root.right))
        balance = self.balance(root)
        if balance > 1 and root.left.value > val:
            return self.rotateR(root)
        if balance < -1 and val > root.right.value:
            return self.rotateL(root)
        if balance > 1 and val > root.left.value:
            root.left = self.rotateL(root.left)
            return self.rotateR(root)
        if balance < -1 and val < root.right.value:
            root.right = self.rotateR(root.right)
            return self.rotateL(root)
        return root

    def preorder(self, root):
        if root is None:
            return
        print(root.value)
        self.preorder(root.left)
        self.preorder(root.right)
        
    def delete(self, val, Node):
        if Node is None:
            return Node
        elif val < Node.value:
            Node.left = self.delete(val, Node.left)
        elif val > Node.value:
            Node.right = self.delete(val, Node.right)
        else:
            if Node.left is None:
                lt = Node.right
                Node = None
                return lt
            elif Node.right is None:
                lt = Node.left
                Node = None
                return lt
            rgt = self.MinimumValueNode(Node.right)
            Node.value = rgt.value
            Node.right = self.delete(rgt.value, Node.right)
        if Node is None:
            return Node
        Node.height = 1 + max(self.height(Node.left), self.height(Node.right))
        balance = self.balance(Node)
        if balance > 1 and self.balance(Node.left) >= 0:
            return self.rotateR(Node)
        if balance < -1 and self.balance(Node.right) <= 0:
            return self.rotateL(Node)
        if balance > 1 and self.balance(Node.left) < 0:
            Node.left = self.rotateL(Node.left)
            return self.rotateR(Node)
        if balance < -1 and self.balance(Node.right) > 0:
            Node.right = self.rotateR(Node.right)
            return self.rotateL(Node)
        return Node

        
Tree=AVL()
rt=None
rt=Tree.insert(3,rt)
rt = Tree.insert(5, rt)
rt = Tree.insert(7, rt)
print("PREORDER")
Tree.preorder(rt)
rt = Tree.insert(1, rt)
rt = Tree.insert(2, rt)
print("PREORDER")
Tree.preorder(rt)
rt = Tree.insert(4, rt)
rt = Tree.insert(6, rt)
rt = Tree.delete(7, rt)
rt = Tree.insert(8, rt)
rt = Tree.insert(9, rt)
print("PREORDER")
Tree.preorder(rt)
rt = Tree.delete(3, rt)
print("PREORDER")
Tree.preorder(rt)
class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
        
class Tree:
    def add(self,value,root):<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09925746325200788, 'fraction_numerical': 0.006465626104965399, 'mean_word_length': 1.7341527413340698, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '376003', 'license': 'MIT', 'n_tokens_mistral': 6069, 'n_tokens_neox': 5887, 'n_words': 1340, 'path': 'Python/trees.ipynb', 'repo_name': 'AkashShaw27/Hacktober20fest21', 'size': '19797'}