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"

Advertisements

4 thoughts on “Size and Height of a Binary Tree

  1. Pingback: Tree Walks and Traversals | codeatsociallywired

  2. hey there and thank you for your info – I have definitely picked
    up something new from right here. I did however expertise several
    technical points using this web site, since I experienced to reload the web
    site many times previous to I could get it to load correctly.
    I had been wondering if your web hosting is OK?
    Not that I am complaining, but sluggish loading instances times will very frequently
    affect your placement in google and can damage your quality score if ads and marketing with Adwords.

    Anyway I’m adding this RSS to my email and can look out for a lot more of your respective intriguing content. Ensure that you update this again very soon.

  3. Good post. I learn something totally new and challenging on blogs I stumbleupon everyday.
    It will always be exciting to read articles from other authors
    and practice a little something from other websites.

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