Python Program to find the level of an input Binary Tree that has the maximum or

highest number of nodes.This program takes as input a Binary Tree as shown below.

The algorithm works recursively by finding the number of nodes at a each level of

the tree by calling the getNodesAtLevel for each nodes of the tree starting with root

where the current level is 0.A loop calls the function for each level and breaks

when it goes past the deepest level i.e.number of nodes=0.
In this program, the following Binary Tree is created and used.
/*The BST tree
10
/ \
/ \
20 30
/ \ /
/ \ /
23 27 29
\
\
9

Input : the above Binary Tree

Output:Maximum number of nodes (3) are at level: 2
#Program to find the level with maximum number of nodes in a Binary Tree
class Node(object):
#Constructor
def __init__(self,data):
self.data=data
self.left=None
self.right=None
#Function to find the nodes at a desired level by recursively getting the nodes from left and right subtrees
def getNodesAtLevel(root,current,desired):
if (root == None):
return 0
if(current==desired):
return 1
return getNodesAtLevel(root.left,current+1,desired) + getNodesAtLevel(root.right,current+1,desired)
# main
if __name__ == '__main__':
# create the binary tree
root=Node(10)
root.left=Node(20)
root.right=Node(30)
root.left.left=Node(23)
root.left.right=Node(27)
root.right.left=Node(29)
root.left.left.right=Node(9)
max_nodes=0 # variable to store the highest number of nodes at a level
max_nodes_level=0 #variable to store the level that has the highest # of nodes
# loop to get nodes at each level starting at level 0 i.e. root the loop runs until

#the level of deepest node or 9999999 ,whichever comes first
for i in range (0,9999999):
num_of_nodes=getNodesAtLevel(root,0,i)
#loop breaks after the deepest level of the tree is crossed as the number of nodes returns 0
if (num_of_nodes==0):
break
else:
if (num_of_nodes>max_nodes):
max_nodes_level=i
max_nodes=num_of_nodes
print('Maximum number of nodes ('+ str(max_nodes)+ ') are at level: '+str(max_nodes_level) )

## Comments