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"
Advertisement

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:
graphForBfsAndDfs

'''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"

Inorder Traversal Of Binary Tree

Although recursion is a very easy way of traversing through Binary Tree but it can easily cause memory problems. The iterative solution can be handy in such cases. A very good explanation of iterative inorder traversal of Binary Tree can be found in the following video produced by Saurabh.

I have implemented using python.


'''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 inOrderTraversalRecursive(tree):
    if tree == None:
        return
    else:
        inOrderTraversal(tree.leftChild)
        print tree.root
        inOrderTraversal(tree.rightChild

#iterative function for inorder traversal of binary tree
def inOrderTraversalIterative(tree)
    current = tree
    stack = []
    done = True
    
    while(done):
        if current:
            stack.append(current)
            current = current.getLeftChild()   
        else:
            if stack == []:
                done = True
            else:
                current = stack.pop()
                print current.root
                current = current.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 "Inorder traversal of tree recursively is:", inOrderTraversalRecursive(r)
    print "\n\n"
    print "Inorder traversal of the tree iteratively is:", inOrderTraversalIterative(r)
    print "\n\n"


Detecting Cycles in Linked List (Hare and Tortoise)

The problem is as follows:
Check whether the given linked list is NULL terminated or ends in a cycle.

Sample Input: 1->2->3->4->5->6->7->8->3
where the numbers 1,2… are the positions in the linked list instead of actual entries.
The node at the 8th position again points to the node at the 3rd position forming a cycle.

Sample Output: True

A very good discussion of how the cycles are detected can be found in wikipedia over here:http://en.wikipedia.org/wiki/Cycle_detection

The Floyds’ algorithm commonly referred as tortoise and hare method is often used for detecting cycles. It could be an interesting read.
tortoise-and-hare

We can think of a hare and a tortoise running on a track. The faster running hare will catch up with the tortoise if they are running in a loop.

The basic algorithm is as follows:
Step 1. Start Tortoise and Hare at the first node of the List.
Step 2. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
Step 3. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
Step 4. If Hare and Tortoise pointing to same Node return, we found loop in the List.
Else start with STEP-2.

'''Complexity
Space : O(n) Time: O(1)'''


class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def setData(self,data):
        self.data = data
    
    def getData(self):
        return self.data
    
    def setNext(self, next):
        self.next = next
        
    def getNext(self):
        return self.next
    
    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None
    
    def insertAtBeg(self,item):
        node = Node(item)
        node.setNext(self.head)
        self.head = node
        
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    
    def search(self,item):
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                
        return found
    
    def insertAtEnd(self,item):
        current = self.head
        
        while current.getNext() != None:
            current = current.getNext()
            
        node = Node(item)
        current.setNext(node)
        
    def insertBeforeItem(self,inItem,item):
        current = self.head
        previous = None
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
                previous = current
                current = current.getNext()
                
        node = Node(inItem)
        previous.setNext(node)
        node.setNext(current)
        
        
    def insertAfterItem(self,inItem,item):
        current = self.head
        
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
#                previous = current
                current = current.getNext()
        successor = current.getNext()       
        node = Node(inItem)
        current.setNext(node)
        node.setNext(successor)
        
            
        
        
        
    def printList(self):
        current = self.head
        
        while current != None:
            print current.getData()
            current = current.getNext()
            
            
    def remove(self,item):
        found = False
        current = self.head
        previous = None
        
        while current.getNext() != None and not found:
            if current.getData() == item:
                print current.getData()
                print previous.getData()
                found = True
                previous.setNext(current.next)
            else:
                previous = current
                current = current.getNext()
                
    def induceCycle(self,end,start):
        current = self.head
        stop = False
        endnodeFound = False
        endnodePointer = None
        count = 0
        while current!= None and not stop:
            count += 1
            if count == end:
                endnodeFound = True
                endnodePointer = current.getNext()
                
            else:
                if count == start:
                    stop = True
                else:
                    current = current.getNext()
                    
        current.setNext(endnodePointer)
        
    def detectCycle(self):
        hare = self.head
        tortoise = self.head
        
        while (hare and tortoise):
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            if hare == None:
                return False
            
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            tortoise = tortoise.getNext()
            
        
        
        
                
        
        
            
        
        
if __name__ == "__main__":
    ll = LinkedList()
    ll.insertAtBeg(1)
    ll.insertAtBeg(2)
    ll.insertAtEnd(3)
    ll.insertBeforeItem(4, 3)
    ll.insertAfterItem(5, 1)
    ll.insertAtEnd(6)
    ll.insertAtEnd(8)
    ll.insertAtEnd(7)
    
    
    ll.printList()
    
    ll.induceCycle(2, 8)
    print ll.detectCycle()