Trees

Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on general trees and binary trees by Prof Naveen Garg.

Some very important properties of a binary tree assuming that the height of the tree is h are:

1. The maximum number of nodes at each level of a binary tree is: 2^l where l is the level number.

2. The number of nodes n in a full binary tree are: 2^h+1-1
This is because a binary tree of height h has h levels. So we add the number of nodes at each level
(2⁰+2¹+2²…2^h)

3. The number of leaf nodes in a full binary tree is: 2^h

Here is the python implementation of a binary tree:

class BinaryTree:
    #binary tree constructor
    def __init__(self, root):
        self.root = root
        self.leftChild = None #initializing left child of a binary tree
        self.rightChild = None #initializing right child of a binary tree
    
    #method for setting the root of a binary tree    
    def setRoot(self, root):
        self.root = root
    
    #method for getting the root of a binary tree    
    def getRoot(self):
        return self.root
    
    #method for getting the left child of the binary tree
    def getLeftChild(self):
        return self.leftChild
    
    #method for getting the right child of the binary tree
    def getRightChild(self):
        return self.rightChild
    
    #method for inserting the left child of the binary tree
    def insertLeftChild(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
    
    #method for inserting the right child of the binary tree        
    def insertRightChild(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

Advertisement