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"

Advertisements

One thought on “Maximum 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