Question

. Let BT Node be the class we often use for binary-tree nodes. Write the following recursive methods: (a) numLeaves: a method that takes a BT Node T as parameter and returns the number of leaves in the tree rooted at T. (b) isEven: a boolean method that takes a BT Node T and checks whether its tree is strictly binary: every node in the tree has an even number of children.

Answer 1

class BT: 
  
    # Constructor of the BT class for creating the nodes of the Tree 
    def __init__(self , key): 
        self.key = key 
        self.left = None
        self.right = None
  
 
def isEven(T): 
  
    #If current node of Tree is empty
    if T is None:     
        return True
      
    #If current node of Tree is a leaf node: No of leaves is 0 i.e Even case
    if T.left is None and T.right is None: 
        return True
  
    #If both the left and the right subtrees are not None and 
    #both left and right subtrees are even 
    #(Case of 2 childs as current node has 2 childs 
    # we recursively check for both left and right childs of
    # current node of Tree).
    if T.left is not None and T.right is not None: 
        return (isEven(T.left) and isEven(T.right)) 
      
    # We reach here when none of the above if condiitions work 
    return False
    
def numberLeaves(T):
    #If current node of Tree is null return 0
    if T is None: 
        return 0 
    #If the current node of Tree has no left and right node 
    #return 1 
    if(T.left is None and T.right is None): 
        return 1 
    #Else call numberLeaves for left and right node recursively
    #and add both to get total leaves from both side
    else:
        return numberLeaves(T.left) + numberLeaves(T.right)
  
# Driver Program 
root = BT(10) 
root.left = BT(20) 
root.right = BT(30) 
  
root.left.right = BT(40)
root.left.left = BT(50) 

#The given Binary Tree in this case.  
#            10
#          /   \
#         20   30
#       /   \     
#      40   50  
#The BT is even and has 3 leaves.

#Checking is given Binary Tree is even or not
#using the isEven()
if isEven(root): 
    print("The given Binary tree is Even")
else: 
    print("The given Binary tree is not Even")
#Calling numberLeaves() and printing the number of leaves in 
#given Binary Tree
print("Number of leaves in given Binary Tree is: ",numberLeaves(root))

Output Screenshot:

(Note: Please refer to the screenshot of the code to understand the indentation of the code.)

Code Screenshots:

BT node:   

isEven():

numberLeaves():

main function: