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

One thought on “Searching an Element in a Binary Tree

  1. Pingback: Tree Walks and Traversals | codeatsociallywired

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s