# Python Program to Count Non Leaf Nodes in a Tree

This is a Python program to count the number of non-leaf nodes in a tree.

Problem Description

The program creates a tree and counts the number of non-leaf nodes in the tree.

Problem Solution

1. Create a class Tree with instance variables key and children.
2. Define methods set_root, add, count_nonleaf_nodes and search.
3. The method set_root takes a key as argument and sets the instance variable key equal to it.
4. The method add appends a node to the list children.
5. The method search returns a node with a specified key.
6. The method count_nonleaf_nodes counts the number of non-leaf nodes and returns it.

Program/Source Code

Here is the source code of a Python program to count the number of non-leaf nodes in a tree. The program output is shown below.

```class Tree:
def __init__(self, data=None):
self.key = data
self.children = []

def set_root(self, data):
self.key = data

self.children.append(node)

def search(self, key):
if self.key == key:
return self
for child in self.children:
temp = child.search(key)
if temp is not None:
return temp
return None

def count_nonleaf_nodes(self):
nonleaf_count = 0
if self.children != []:
nonleaf_count = 1
for child in self.children:
nonleaf_count = nonleaf_count + child.count_nonleaf_nodes()
return nonleaf_count

tree = None

print('Menu (this assumes no duplicate keys)')
print('count')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0].strip().lower()
data = int(do[1])
new_node = Tree(data)
suboperation = do[2].strip().lower()
if suboperation == 'at':
tree = new_node
elif suboperation == 'below':
position = do[3].strip().lower()
key = int(position)
ref_node = None
if tree is not None:
ref_node = tree.search(key)
if ref_node is None:
print('No such key.')
continue

elif operation == 'count':
if tree is None:
print('Tree is empty.')
else:
count = tree.count_nonleaf_nodes()
print('Number of nonleaf nodes: {}'.format(count))

elif operation == 'quit':
break```
Program Explanation

1. A variable is created to store the binary tree.
2. The user is presented with a menu to perform operations on the tree.
3. The corresponding methods are called to perform each operation.
4. The method count_nonleaf_nodes is called on the tree to calculate the number of non-leaf nodes in the tree.

Runtime Test Cases
```Case 1:
Menu (this assumes no duplicate keys)
count
quit
What would you like to do? add 1 at root
What would you like to do? count
Number of nonleaf nodes: 0
What would you like to do? add 2 below 1
What would you like to do? add 3 below 1
What would you like to do? count
Number of nonleaf nodes: 1
What would you like to do? add 4 below 2
What would you like to do? count
Number of nonleaf nodes: 2
What would you like to do? add 5 below 4
What would you like to do? count
Number of nonleaf nodes: 3
What would you like to do? quit

Case 2:
Menu (this assumes no duplicate keys)
count
quit
What would you like to do? add 1 at root
What would you like to do? add 2 below 1
What would you like to do? add 3 below 2
What would you like to do? add 4 below 3
What would you like to do? add 5 below 4
What would you like to do? count
Number of nonleaf nodes: 4
What would you like to do? add 6 below 4
What would you like to do? count
Number of nonleaf nodes: 4
What would you like to do? add 7 below 6
What would you like to do? count
Number of nonleaf nodes: 5
What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]