class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None
def setRoot(self, root):
self.root = root
def getRoot(self):
return self.root
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
'''Iterative Level Order Traversal of a Binary Tree'''
def iterativeLevelOrderTraversal(tree):
current = tree
queue = []
queue.append(current)
while (queue != []):
temp = queue.pop(0)
print temp.root
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
'''Printing Level Order Traversal in a reverse way'''
def printingLevelOrderReverse(tree):
stack = []
if tree == None:
return 0
else:
queue = []
queue.append(tree)
while(queue != []):
temp = queue.pop(0)
stack.append(temp.root)
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
if stack != []:
for i in range(len(stack)):
print stack.pop()
else:
return 0
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "Levelorder traversal of the tree is:", iterativeLevelOrderTraversal(r)
print "\n\n"
print "Printing level order in a reverse way:", printingLevelOrderReverse(r)
print "\n\n"
Author Archives: debanjanbhucs
Size and Height of a Binary Tree
class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None
def setRoot(self, root):
self.root = root
def getRoot(self):
return self.root
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
'''recursive process for finding height of a binary tree'''
def height(tree):
if tree == None:
return 0
else:
return max(height(tree.leftChild),height(tree.rightChild)) + 1
'''iterative process for finding height of a binary tree'''
def heightIterative(tree):
height = 0
if tree == None:
return 0
queue = []
queue.append(tree)
queue.append("NULL")
while ( queue != []):
root = queue.pop(0)
if root == "NULL":
if queue != []:
queue.append("NULL")
height += 1
else:
if root.getLeftChild():
queue.append(root.getLeftChild())
if root.getRightChild():
queue.append(root.getRightChild())
return height
'''recursive process for finding size of a binary tree'''
def size(tree):
if tree == None:
return 0
else:
return size(tree.getLeftChild()) + 1+ size(tree.getRightChild())
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "Height of the tree is:", height(r)
print "\n\n"
print "size of the tree is:", size(r)
print "\n\n"
print "height of the tree is:", heightIterative(r)
print "\n\n"
Searching an Element in a Binary Tree
class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None
def setRoot(self, root):
self.root = root
def getRoot(self):
return self.root
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
'''Recursive method for searching an element in a tree'''
def searchingElementRecursive(tree,element):
if tree == None:
return False
else:
if tree.root == element:
return True
else:
temp = searchingElementRecursive(tree.leftChild,element)
if temp != 0:
return temp
else:
return searchingElementRecursive(tree.rightChild,element)
'''Iterative method for searching an element in a tree'''
def searchingElementIterative(tree,element):
queue = []
# current = tree
queue.append(tree)
if tree == None:
return False
while (queue != []):
temp = queue.pop(0)
if temp.root == element:
return True
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return False
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "Search for element 63", searchingElementRecursive(r,63)
print "\n\n"
print "Search for element 36", searchingElementRecursive(r,36)
print "\n\n"
print "Search for element 63", searchingElementIterative(r,63)
print "\n\n"
print "Search for element 36", searchingElementIterative(r,36)
print "\n\n"
Maximum Element in A Binary Tree
class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None
def setRoot(self, root):
self.root = root
def getRoot(self):
return self.root
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
'''recursive way to find the maximum element of a tree'''
def maximumElement(tree):
max = 0
if tree == None:
return
else:
rootValue = tree.root
left = maximumElement(tree.leftChild)
right = maximumElement(tree.rightChild)
if left > right:
max = left
else:
max = right
if rootValue > max:
max = rootValue
return max
'''iterative way to find the maximum element of a tree'''
def maximumElementIterative(tree):
queue = []
current = tree
max = 0
queue.append(tree)
if tree == None:
return 0
else:
while (queue != []):
temp = queue.pop(0)
if max <= temp.root:
max = temp.root
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return max
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "The maximum element in the tree recursively is:", maximumElement(r)
print "\n\n"
print "The maximum element in the tree iteratively is:", maximumElementIterative(r)
print "\n\n"
Breadth First and Depth First Traversal
Here is the graph that has to be traversed:
'''graph representation'''
graph = {1:[2,3], 2:[4,5], 3:[6], 4:None, 5:[7,8], 6:None, 7:None, 8:None}
def breadthFirstTraversal(graph,start):
visited = []
tobevisited = [start]
while len(tobevisited) > 0:
currentNode = tobevisited.pop(0)
if currentNode not in visited:
visited += [currentNode]
if graph[currentNode] is not None:
tobevisited = tobevisited + graph[currentNode]
return visited
print breadthFirstTraversal(graph,1)
'''Output: [1, 2, 3, 4, 5, 6, 7, 8]'''
def depthFirstTraversal(graph,start):
visited = []
tobevisited = [start]
while len(tobevisited) > 0:
currentNode = tobevisited.pop(0)
if currentNode not in visited:
visited += [currentNode]
if graph[currentNode] is not None:
tobevisited = graph[currentNode] + tobevisited
return visited
print depthFirstTraversal(graph,1)
'''Output: [1, 2, 4, 5, 7, 8, 3, 6]'''
Quick Sort
Have a look at this video and learn quick sort with Hungarian Folk Dance.
Here is another very good video that illustrates quick sort.
Here are some different ways of implementing quick sort in Python.
import random
from random import randrange
mylist = [3,0,1,8,7,2,5,4,9,6]
def qsort1(mylist):
if mylist == []:
return []
else:
pivot = mylist[0]
lesser = qsort1([x for x in mylist[1:] if x < pivot])
greater = qsort1([x for x in mylist[1:] if x >= pivot])
return lesser + [pivot] + greater
print qsort1(mylist)
def partition(mylist, l, e, g):
while mylist != []:
head = mylist.pop(0)
if head < e[0]:
l = [head] + l
if head > e[0]:
g = [head]+ g
if head == e[0]:
e = [head] + e
return (l,e,g)
def qsort2(mylist):
if mylist == []:
return []
else:
pivot = mylist[0]
lesser,equal,greater = partition(mylist[1:],[],list([pivot]),[])
return qsort2(lesser)+equal+qsort2(greater)
print qsort2(mylist)
This one works for any randomly chosen pivot element.
def qsort1a(list):
def qsort(list):
if list == []:
return []
else:
pivot = list.pop(randrange(len(list)))
lesser = qsort([l for l in list if l < pivot])
greater = qsort([l for l in list if l >= pivot])
return lesser + [pivot] + greater
return qsort(list[:])
print qsort1a(mylist)
Merge Sort
Learn Merge Sort with Transylvanian Saxon and German Folk dance:
The python code for Merge Sort is as follows:
mylist = [4,2,8,6,0,5,1,7,3,9]
def merge(left, right):
mergedList = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
mergedList.append(left[i])
i += 1
else:
mergedList.append(right[j])
j += 1
mergedList += left[i:]
mergedList += right[j:]
return mergedList
def mergesort(lst):
if len(lst) <=1:
return lst
else:
middle = int(len(lst)/2)
left = mergesort(lst[:middle])
right = mergesort(lst[middle:])
return merge(left,right)
print mergesort(mylist)
Insertion Sort and Shell Sort – the two brothers
A good explanation of insertion sort can be found over here:
I personally like this video a lot:
itemList = [4,28,56,3,89,90,126]
def insertion_sort(itemList):
for i in range(1,len(itemList)):
value = itemList[i]
j = i
while (j-1 >= 0 and value < itemList[j-1]):
itemList[j]=itemList[j-1]
j-=1
itemList[j] = value
return itemList
print insertion_sort(itemList)
You can find a similar video for shell sort:
def shell_sort(itemList):
gap = len(itemList)//2
while (gap > 0):
for i in range(gap,len(itemList)):
value = itemList[i]
j = i
while (j-gap >= 0 and value < itemList[j-gap]):
itemList[j] = itemList[j-gap]
j -= gap
itemList[j] = value
gap //= 2
return itemList
print shell_sort(itemList)
Count Sort
A very good explanation of Count Sort is provided by Saurabh over here:
I tried to implement it in the simplest possible way in python.
arr = [1,2,4,5,7,7,8,9,11,13,11,9,14,15,6,5,4,3,2,1,1,0,0,1]
def countSort(arr):
maxValue = max(arr)+1
print maxValue
count = [0]*maxValue
for entries in arr:
count[entries] += 1
sortedarray = []
for i in range(len(count)):
sortedarray += [i]*count[i]
return sortedarray
Preorder Traversal of Binary Tree
Here is the code for iterative preorder traversal of binary trees.
'''class implementing binary tree'''
'''Binary Tree Class and its methods'''
class BinaryTree:
def __init__(self, root):
self.root = root #root node
self.leftChild = None #left child
self.rightChild = None #right child
#set root node
def setRoot(self, root):
self.root = root
#get root node
def getRoot(self):
return self.root
#get left child of a node
def getLeftChild(self):
return self.leftChild
#get right child of a node
def getRightChild(self):
return self.rightChild
#insert a left child of a node
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
#insert a right child of a node
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
#recursive function for inorder traversal of binary tree
def preOrderTraversalRecursive(tree):
if tree == None:
return
else:
print tree.root
preOrderTraversal(tree.leftChild)
preOrderTraversal(tree.rightChild)
#iterative function for inorder traversal of binary tree
def preOrderTraversalIterative(tree)
stack = []
if tree == None:
return
stack.append(tree)
while(stack != []):
node = stack.pop()
print node.root
if node.getRightChild():
stack.append(node.getRightChild())
if node.getLeftChild():
stack.append(node.getLeftChild())
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "Preorder traversal of tree recursively is:", preOrderTraversalRecursive(r)
print "\n\n"
print "Preorder traversal of the tree iteratively is:", preOrderTraversalIterative(r)
print "\n\n"
codeatsociallywired 