BINARY TREE class btree: class node: def __init__(self): self.data=0 self.parent=None self.lc=None self.rc=None def inorder(self,v): if(v==None): return self.inorder(v.lc) print(v.data,end=",") self.inorder(v.rc)

def preorder(self,v):
    if(v==None):
        return
    print(v.data,end=",")
    self.preorder(v.lc)
    self.preorder(v.rc)

def postorder(self,v):
    if(v==None):
        return
    self.postorder(v.lc)
    self.postorder(v.rc)
    print(v.data,end=",")
def levelorder(self,v):
    l=[]
    l.append(v)
    while(len(l)!=0):
        print(l[0].data,end=",")
        if(l[0].lc!=None):
            l.append(l[0].lc)
        if(l[0].rc!=None):
            l.append(l[0].rc)
        l.pop(0)
def isext(self,val):
    return (val.lc==None and val.rc==None)
def __init__(self):
    self.sz=0
    self.root=self.node()
def isroot(self,var):
    if(var.parent!=None):
        return False
    else:
        return True
def isEmpty(self):
    return (self.sz==0)
def size(self):
    return self.sz
def printchild(self,var):
    c=[]
    if(var.lc!=None):
        c.append(var.lc)
    if(var.rc!=None):
        c.append(var.rc)
    return c
def printlist(self,s):
    print(None,end=" ")
    for i in range(1,len(s)):
        print(s[i].data,end=",")
    print()
def build(self,s):
    rs=[]
    for i in range(len(s)):
        if(i==0 and s[i]==-1):
            rs.append(None)
        else:
            temp = self.node()
            temp.data = s[i]
            if(i!=1):
                temp.parent = rs[i//2]
                if(i%2==0):
                    rs[i//2].lc=temp
                else:
                    rs[i//2].rc=temp
            rs.append(temp)
    self.root=rs[1]
    self.sz=len(rs)
    return rs
def depth(self,v):
    if(v.parent==None):
        return 0
    return 1 + self.depth(v.parent)
def height(self,v):
    if(v==None):
        return -1
    return max(self.height(v.lc),self.height(v.rc))+1
def delleaf(self,v):
    if(v==None):
        return None
    if(self.isext(v)):
        return None
    v.lc=self.delleaf(v.lc)
    v.rc=self.delleaf(v.rc)
    return v
def isproper(self,v):
    if(v==None):
        return True
    if(v.lc==None and v.rc==None):
        return True
    if(v.lc!=None and v.rc!=None):
        return self.isproper(v.lc) and self.isproper(v.rc)
    return False
def mirror(self,v):
    if(v==None):
        return None
    self.mirror(v.lc)
    self.mirror(v.rc)
    temp=v.lc
    v.lc=v.rc
    v.rc=temp
def root2leafsum(self,v,k,cs,lis):
    if(v==None):
        return
    cs=cs+v.data
    if(v.lc==None and v.rc==None and cs==k):
        lis.append(0)
    self.root2leafsum(v.lc,k,cs,lis)
    self.root2leafsum(v.rc,k,cs,lis)
    cs=cs-v.data
    lis.append(1)
def r2ls(self,k):
    x=self.root
    cs=0
    lis=[]
    self.root2leafsum(x,k,cs,lis)
    if 0 in lis:
        print("True")
    else:
        print("False")
def iscomplete(self,v):
    if(v==None):
        return True
    q=[]
    q.append(v)
    flag=False
    while(len(q)):
        temp=q.pop(0)
        if(temp.lc):
            if(flag==True):
                return False
            q.append(v.lc)
        else:
            flag=True
        if(temp.rc):
            if(flag==True):
                return False
            q.append(v.rc)
        else:
            flag=True
    return True

def leastleaf(self,v,ps,cs):
    if(v==None):
        return
    cs+=v.data
    if(v.lc==None and v.rc==None):
        ps.append((cs,v.data))
    self.leastleaf(v.lc,ps,cs)
    self.leastleaf(v.rc,ps,cs)
    cs-=v.data
def ll(self):
    x=self.root
    cs=0
    ps=[]
    self.leastleaf(x,ps,cs)
    lef=0
    min=ps[0][0]
    for i in range(len(ps)):
        if(min>=ps[i][0]):
            min=ps[i][0]
            lef=ps[i][1]
    print(lef)

def findADepth(node): d = 0 while (node != None): d += 1 node = node.left return d

This function tests if a binary tree

is perfect or not. It basically checks

for two things :

1) All leaves are at same level

2) All internal nodes have two children

def isPerfectRec(root, d, level = 0):

# An empty tree is perfect
if (root == None):
    return True

# If leaf node, then its depth must
# be same as depth of all other leaves.
if (root.left == None and root.right == None):
    return (d == level + 1)

# If internal node and one child is empty
if (root.left == None or root.right == None):
    return False

# Left and right subtrees must be perfect.
return (isPerfectRec(root.left, d, level + 1) and
        isPerfectRec(root.right, d, level + 1))

def isbalanced(self,v): if(v==None): return True return abs(self.height(v.lc)-self.height(v.rc))<=1 and self.isbalanced(v.lc) and self.isbalanced(v.rc) t = btree() x = [-1,11,12,13,14,15,16] rx =t.build(x) t.printlist(rx) s=t.root.lc rc = t.printchild(s) for i in rc: print(i.data,end=",") print() print(t.isext(t.root.lc)) t.inorder(t.root) print() t.preorder(t.root) print() t.postorder(t.root) print() t.levelorder(t.root) print() print(t.isproper(t.root)) print(t.depth(t.root.lc.lc)) print(t.height(t.root)) t.r2ls(37) t.ll() t.delleaf(t.root) t.levelorder(t.root) print() t.mirror(t.root) t.levelorder(t.root) print()

MINHEAP

same code but changed > sign in comparisons to <

class binheap: def __init__(self): self.data=[] self.sz=0 def getparent(self,index): return (index-1)//2 def getlc(self,index): return 2index +1 def getrc(self,index): return 2index +2 def hasparent(self,index): return self.getparent(index)>=0 def haslc(self,index): return self.getlc(index)<self.sz def hasrc(self,index): return self.getrc(index)<self.sz def parent(self,index): return self.data[self.getparent(index)] def leftchild(self,index): return self.data[self.getlc(index)] def rightchild(self,index): return self.data[self.getrc(index)] def swap(self,i1,i2): temp=self.data[i1] self.data[i1]=self.data[i2] self.data[i2]=temp def insert(self,val): self.data.append(val) self.sz+=1 self.upheap(self.sz-1) def upheap(self,index): if(self.hasparent(index) and self.parent(index)>self.data[index]): self.swap(index,self.getparent(index)) self.upheap(self.getparent(index)) return def getminval(self): return self.data[0] def removemin(self): if(self.sz==0): print("Empty") return val=self.data[0] self.data[0]=self.data[self.sz-1] self.data.pop() self.sz-=1 self.downheap(0) return val def downheap(self,index): minval=index if(self.haslc(index)and self.data[minval]>self.leftchild(index)): minval=self.getlc(index) if(self.hasrc(index)and self.data[minval]>self.rightchild(index)): minval=self.getrc(index) if(minval!=index): self.swap(minval,index) self.downheap(minval) return def buildheap(self,lis): for i in lis: self.insert(i) def size(self): return self.sz def leveltrav(self): for i in self.data: print(i,end=" ") print() lis=[23,3,32,1,19,26,54,9] b=binheap() b.buildheap(lis) print(b.size()) b.leveltrav() b.insert(10) b.leveltrav() print(b.removemin()) b.leveltrav()

MAXHEAP class binheap: def __init__(self): self.data=[] self.sz=0 def getparent(self,index): return (index-1)//2 def getlc(self,index): return 2index +1 def getrc(self,index): return 2index +2 def hasparent(self,index): return self.getparent(index)>=0 def haslc(self,index): return self.getlc(index)<self.sz def hasrc(self,index): return self.getrc(index)<self.sz def parent(self,index): return self.data[self.getparent(index)] def leftchild(self,index): return self.data[self.getlc(index)] def rightchild(self,index): return self.data[self.getrc(index)] def swap(self,i1,i2): temp=self.data[i1] self.data[i1]=self.data[i2] self.data[i2]=temp def insert(self,val): self.data.append(val) self.sz+=1 self.upheap(self.sz-1) def upheap(self,index): if(self.hasparent(index) and self.parent(index)<self.data[index]): self.swap(index,self.getparent(index)) self.upheap(self.getparent(index)) return def getminval(self): return self.data[0] def removemax(self): if(self.sz==0): print("Empty") return val=self.data[0] self.data[0]=self.data[self.sz-1] self.data.pop() self.sz-=1 self.downheap(0) return val def downheap(self,index): maxval=index if(self.haslc(index)and self.data[maxval]<self.leftchild(index)): maxval=self.getlc(index) if(self.hasrc(index)and self.data[maxval]<self.rightchild(index)): maxval=self.getrc(index) if(maxval!=index): self.swap(maxval,index) self.downheap(maxval) return def buildheap(self,lis): for i in lis: self.insert(i) def size(self): return self.sz def leveltrav(self): for i in self.data: print(i,end=" ") print() lis=[23,3,32,1,19,26,54,9] b=binheap() b.buildheap(lis) print(b.size()) b.leveltrav() b.insert(10) b.leveltrav() print(b.removemax()) b.leveltrav()

BST class node: def __init__(self,val=0): self.data=val self.parent=None self.lc=None self.rc=None

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

def insert(self,v,val):
    xnode= node(val)
    if(self.root==None):
        self.root=xnode
        return
    if(val>v.data):
        if(v.rc==None):
            v.rc=xnode
            v.rc.parent=v
        else:
            self.insert(v.rc,val)
    if(val<v.data):
        if(v.lc==None):
            v.lc=xnode
            v.lc.parent=v
        else:
            self.insert(v.lc,val)

def buildtree(self,lis):
    for i in lis:
        self.insert(self.root,i)

def depth(self,v):
    if(v==None):
        return
    if(v.parent==None):
        return 0
    else:
        return 1+self.depth(v.parent)

def findele(self,v,ele):
    if(v==None):
        return
    if(ele<v.data):
        return self.findele(v.lc,ele)
    if(ele>v.data):
        return self.findele(v.rc,ele)
    if(v.data==ele):
        print("True")

def leveltrav(self,v):
    lis=[]
    lis.append(v)
    while(len(lis)!=0):
        print(lis[0].data,end=" ")
        if(lis[0].lc!=None):
            lis.append(lis[0].lc)
        if(lis[0].rc!=None):
            lis.append(lis[0].rc)
        lis.pop(0)
    print()
def getnode(self,v,ele):
    if(v==None):
        return v
    if(v.data==ele):
        return v 
    if(ele>v.data):
        return self.getnode(v.rc,ele)
    if(ele<v.data):
        return self.getnode(v.lc,ele)
def isext(self,v):
    if(v==None):
        return False
    if(v.lc==None and v.rc==None):
        return True
    else:
        return False
def isint(self,v):
    if(v==None):
        return False
    if(v.lc!=None or v.rc!=None):
        return True
    else:
        return False
def isroot(self,v):
    if(v==None):
        return False
    if(v.parent==None):
        return True
    else:
        return False
def getchild(self,v):
    lis=[]
    if(v.lc!=None):
        lis.append(v.lc.data)
    if(v.rc!=None):
        lis.append(v.rc.data)
    for i in lis:
        print(i,end=" ")
    print()
def preorder(self,v):
    if(v==None):
        return
    print(v.data,end=" ")
    self.preorder(v.lc)
    self.preorder(v.rc)
def inorder(self,v):
    if(v==None):
        return
    self.inorder(v.lc)
    print(v.data,end=" ")
    self.inorder(v.rc)
def postorder(self,v):
    if(v==None):
        return
    self.postorder(v.lc)
    self.postorder(v.rc)
    print(v.data,end=" ")
def countsz(self,v):
    if(v==None):
        return 0 
    else:
        return 1 + self.countsz(v.lc) + self.countsz(v.rc)
def revleveltrav(self,v):
    lis=[]
    lis.append(v)
    while(len(lis)!=0):
        print(lis[0].data,end=" ")
        if(lis[0].rc!=None):
            lis.append(lis[0].rc)
        if(lis[0].lc!=None):
            lis.append(lis[0].lc)
        lis.pop(0)
    print()
def eulertour(self,v):
    euler=[]
    euler= self.eu(v,euler)
    for i in euler:
        print(i,end=" ")
    print()
def eu(self,v,euler):
    euler.append(v.data)
    if(v.lc!=None):
        euler=self.eu(v.lc,euler)
        euler.append(v.data)
    if(v.rc!=None):
        euler=self.eu(v.rc,euler)
        euler.append(v.data)
    return euler
def insuc(self,v):
    cr=v
    while(cr.lc!=None):
        cr=cr.lc 
    return cr
def deletion(self,v,val):
    if(v==None):
        return
    elif(val>v.data):
        v.rc=self.deletion(v.rc,val)
    elif(val<v.data):
        v.lc=self.deletion(v.lc,val)
    else:
        if(v.lc==None and v.rc==None):
            v=None
        elif(v.lc==None):
            v=v.rc 
        elif(v.rc==None):
            v=v.lc 
        else:
            temp=node(self.insuc(v.rc).data)
            v.data=temp.data
            v.rc=self.deletion(v.rc,temp.data)
    return v
def diameter(self,v):
    if(v==None):
        return 0 
    lh=self.height(v.lc)
    rh=self.height(v.rc)
    ld=self.diameter(v.lc)
    rd=self.diameter(v.rc)
    return max(lh+rh,max(ld,rd))
def height(self,v):
    if(v==None):
        return -1
    else:
        return 1+max(self.height(v.lc),self.height(v.rc))
def mirror(self,v):
    if(v==None):
        return
    else:
        temp=v 
        self.mirror(v.lc)
        self.mirror(v.rc)
        temp=v.lc 
        v.lc = v.rc 
        v.rc=temp

l=[42,54,6,2,34,24,68,70] b=bst() b.buildtree(l) b.leveltrav(b.root)

print(b.root.data)

b.findele(b.root,70) print(b.depth(b.root.lc.rc)) print(b.getnode(b.root,70)) print(b.isext(b.getnode(b.root,64))) print(b.isint(b.getnode(b.root,6))) print(b.isroot(b.getnode(b.root,24))) b.getchild(b.getnode(b.root,42)) b.preorder(b.root) print() b.inorder(b.root) print() b.postorder(b.root) print() print(b.countsz(b.root)) b.revleveltrav(b.root) b.eulertour(b.root) '''print(b.deletion(b.root,42)) b.leveltrav(b.root) print(b.height(b.getnode(b.root,54))) print(b.deletion(b.root,68)) b.leveltrav(b.root)
print(b.deletion(b.root,24)) b.leveltrav(b.root)''' print(b.diameter(b.getnode(b.root,42))) b.mirror(b.root) b.leveltrav(b.root)

GRAPHS """The code is borrowed from the book "Problem Solving with Algorithms and Data Structures" http://interactivepython.org/courselib/static/pythonds/Graphs/graphintro.html

""" from collections import OrderedDict class BinHeap(): def __init__(self): self.heapList = [0] self.currentSize = 0

""" This method defines the upheap function when inserting an element
"""
def upHeapp(self,i):

    while i//2 > 0:
        if self.heapList[i] < self.heapList[i // 2]:
            self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
        i = i // 2

def insert(self,k):
    self.heapList.append(k)
    self.currentSize += 1
    self.upHeapp(self.currentSize)

def size(self):
    return self.currentSize

""" This method defines the downheap function when removing min
"""
def downHeap(self,i):
    while (i * 2) <= self.currentSize:
        min = self.minChild(i)
        if self.heapList[i] > self.heapList[min]:
            self.heapList[i], self.heapList[min] = self.heapList[min], self.heapList[i]
        i = min


def minChild(self,i):
    if (i * 2)+1 > self.currentSize:
        return i * 2
    else:
        if self.heapList[i*2] < self.heapList[(i*2)+1]:
            return i * 2
        else:
            return (i * 2) + 1

def delMin(self):
    if len(self.heapList) == 1:
        return 'Empty heap'
    root = self.heapList[1]
    self.heapList[1] = self.heapList[self.currentSize]
    self.heapList.pop(self.currentSize)
    self.currentSize -= 1
    self.downHeap(1)
    #self.printHeap()
    return root

#create a method to print the contents of the heap in level order 
def printHeap(self):
    print(self.heapList)

'''
Graph ADT starts from here
'''

class Vertex: def __init__(self,key): self.id = key self.connectedTo = {}

def addNeighbor(self,nbr,weight=0):
    self.connectedTo[nbr] = weight

def __str__(self):
    return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

def getConnections(self):
    return self.connectedTo.keys()

def getId(self):
    return self.id

def getWeight(self,nbr):
    return self.connectedTo[nbr]

class Graph: def __init__(self): self.vertList = {} self.numVertices = 0 self.front=[] self.back=[] self.depfs=[] def addVertex(self,key): self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertList[key] = newVertex self.vertList = OrderedDict(sorted(self.vertList.items())) return newVertex

def getVertex(self,n):
    if n in self.vertList:
        return self.vertList[n]
    else:
        return None

def __contains__(self,n):
    return n in self.vertList

def addEdge(self,f,t,cost=0):  #f is from node, t is to node
    if f not in self.vertList:
        nv = self.addVertex(f)
    if t not in self.vertList:
        nv = self.addVertex(t)
    self.vertList[f].addNeighbor(self.vertList[t], cost)

def getVertices(self):
    return self.vertList.keys()


def __iter__(self):
    return iter(self.vertList.values())
"""
Write a method to generate an adjacency matrix representation of the graph
"""
def createAdjMatrix(self):
    adjmat = list()
    #@start-editable@


    for a,vert in self.vertList.items():
        adjmat.append([0]*self.numVertices)
        for neigh in vert.getConnections():
            adjmat[vert.getId()][neigh.getId()]=vert.getWeight(neigh)










    #@end-editable@
    print("Adjacency matrix")
    for i in range(self.numVertices):
        for j in range(self.numVertices):
            print(adjmat[i][j], end=" ")
        print("")
    return

def printdfs(self):
            print("Front edges:",self.front)
            print("Back edges:",self.back)
            print("dfs:",self.depfs)
"""
Write a method to traverse the graph using dfs from start node. 
The function must print the nodes and edges in the order in which 
they are visited, and mention if it is a forward or backward edge.
"""
def dfs(self,stnode):
    self.depfs.append(stnode.getId() )
    neighbours=list(stnode.getConnections())

    #@start-editable@



    for neigh in neighbours:
        if neigh.getId() in self.depfs:
            self.back.append([stnode.getId(),neigh.getId()])
        else:
            self.front.append([stnode.getId(),neigh.getId()])
            self.dfs(neigh)







    #@end-editable@
    return

"""
Write a method to traverse the graph using bfs from start node.  The function must print the nodes and edges in the order in which 
they are visited, and mention if it is a forward or cross edge.
"""
def bfs(self,stnode):
    queue=[]
    breadth=[]
    cross=[]
    breadth.append(stnode.getId())
    queue.append(stnode.getId())

    #@start-editable@


    while queue:
        vert=queue.pop(0)
        for neigh in self.vertList[vert].getConnections():
            if neigh.getId() in breadth:
                cross.append([vert,neigh.getId()])
            else:
                breadth.append(neigh.getId())
                queue.append(neigh.getId()) 








    #@end-editable@
    print("Bfs:",breadth)
    print("Cross edge:",cross)
    return

"""
Write a method to generate the minimum spanning tree of the graph using Kruskal algorithm
"""
def mstKruskal(self):
    wt=BinHeap()
    edge={}
    tree=[]
    re=[]

    #@start-editable@

    for i in self.vertList:
        tree.append({i})
        for j in self.vertList[i].getConnections():
            wt.insert([self.vertList[i].connectedTo[j],i,j.getId()])
    while wt.currentSize:
        temp=wt.delMin()
        for i in tree:
            if temp[1] in i:
                cu =i 
            if temp[2] in i:
                cv=i 
        if cu!=cv:
            re.append([temp[1],temp[2]])
            tm = cu.union(cv)
            tree.append(tm)
            tree.remove(cu)
            tree.remove(cv)        












    #@end-editable@
    print("Minimum spanning tree:",sorted(re))                  
    return

def testGraph():

g = Graph()
for i in range(6):
    g.addVertex(i)
g.vertList
g.addEdge(5, 1, 8)
g.addEdge(1, 2, 19)
g.addEdge(5, 0, 10)
g.addEdge(4, 6, 11)
g.addEdge(6, 10, 23)
g.addEdge(10, 9, 33)
g.addEdge(9, 8, 7)
g.addEdge(6, 7, 6)
g.addEdge(8, 7, 1)
g.addEdge(9, 6, 9)
g.addEdge(7, 10, 14)
g.addEdge(0, 4, 15)
g.addEdge(0, 3, 16)
g.addEdge(0, 2, 5)
g.addEdge(0, 1, 2)
g.addEdge(2, 3, 4)
g.addEdge(3, 4, 30)
g.addEdge(4, 5, 18)
g.addEdge(5, 2, 22)
g.addEdge(3, 1, 17)

for v in g:
    for w in v.getConnections():
        print("( %s , %s )" % (v.getId(), w.getId()))


inputs = int(input())
while inputs > 0:
    command = input()
    operation = command.split()
    if (operation[0] == "A"):
        AdjMat= g.createAdjMatrix()
    elif (operation[0] == "B"):
        start = g.getVertex(int(operation[1]))
        g.bfs(start)
    elif (operation[0] == "D"):
        start = g.getVertex(int(operation[1]))
        g.dfs(start)
        g.printdfs()
    elif (operation[0] == "M"):
        g.mstKruskal()
    inputs-=1

def main(): testGraph()

if __name__ == '__main__': main()

<<<<<<<<<<<GRAPHS>>>>>>>>>>>> def DFSUtil(self, v, visited):

    # Mark the current node as visited
    # and print it
    visited.add(v)
    print(v, end=' ')

    # Recur for all the vertices
    # adjacent to this vertex
    for neighbour in self.graph[v]:
        if neighbour not in visited:
            self.DFSUtil(neighbour, visited)

# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):

    # Create a set to store visited vertices
    visited = set()

    # Call the recursive helper function
    # to print DFS traversal
    self.DFSUtil(v, visited)

<<<<<<<<BFS>>>>>>>>>>> def BFS(self, s):

    # Mark all the vertices as not visited
    visited = [False] * (max(self.graph) + 1)

    # Create a queue for BFS
    queue = []

    # Mark the source node as
    # visited and enqueue it
    queue.append(s)
    visited[s] = True

    while queue:

        # Dequeue a vertex from
        # queue and print it
        s = queue.pop(0)
        print (s, end = " ")

        # Get all adjacent vertices of the
        # dequeued vertex s. If a adjacent
        # has not been visited, then mark it
        # visited and enqueue it
        for i in self.graph[s]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True