Number of Leaves, Non Leaf Nodes and Nodes having one Child 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

def getNumberOfLeavesIterative(tree):
    queue = []
    leafCount = 0
    queue.append(tree)    
    
    if tree == None:
        return 0
    

    while (queue != []):
        temp = queue.pop(0)
        if temp.getLeftChild() == None and temp.getRightChild() == None:
            leafCount += 1
    
        if temp.getLeftChild():
            queue.append(temp.getLeftChild())
            
        if temp.getRightChild():
            queue.append(temp.getRightChild())
                    
    return leafCount

def getNumberOfNonLeafNodesIterative(tree):
    queue = []
    nonleafCount = 0
    queue.append(tree)    
    
    if tree == None:
        return 0
    

    while (queue != []):
        temp = queue.pop(0)
        if temp.getLeftChild() != None and temp.getRightChild() != None:
            nonleafCount += 1
    
        if temp.getLeftChild():
            queue.append(temp.getLeftChild())
            
        if temp.getRightChild():
            queue.append(temp.getRightChild())
                    
    return nonleafCount

def getNumberOfNodesHavingOneChild(tree):
    queue = []
    oneChildCount = 0
    queue.append(tree)    
    
    if tree == None:
        return 0
    

    while (queue != []):
        temp = queue.pop(0)
        if (temp.getLeftChild() == None and temp.getRightChild() != None) or(temp.getLeftChild() != None and temp.getRightChild() == None) :
            oneChildCount += 1
    
        if temp.getLeftChild():
            queue.append(temp.getLeftChild())
            
        if temp.getRightChild():
            queue.append(temp.getRightChild())
                    
    return oneChildCount

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 number of leaf nodes of the binary tree are:",getNumberOfNonLeafNodesIterative(r)
    print "\n\n"

    print "The number of non-leaf nodes of the binary tree are:", getNumberOfNonLeafNodesIterative(r)
    print "\n\n"

    print "The number of nodes having just one child are:", getNumberOfNodesHavingOneChild(r)
    print "\n\n"

Advertisement