Python Program to Count Leaf Nodes in a Tree

«
»

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

Problem Description

The program creates a tree and counts the number of 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_leaf_nodes, count_leaf_nodes_helper 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_leaf_nodes counts the number of leaf nodes and returns it. It calls the recursive method count_leaf_nodes_helper.

Program/Source Code

Here is the source code of a Python program to count the number of 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
 
    def add(self, node):
        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_leaf_nodes(self):
        leaf_nodes = []
        self.count_leaf_nodes_helper(leaf_nodes)
        return len(leaf_nodes)
 
    def count_leaf_nodes_helper(self, leaf_nodes):
        if self.children == []:
            leaf_nodes.append(self)
        else:
            for child in self.children:
                child.count_leaf_nodes_helper(leaf_nodes)
 
 
tree = None
 
print('Menu (this assumes no duplicate keys)')
print('add <data> at root')
print('add <data> below <data>')
print('count')
print('quit')
 
while True:
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'add':
        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
            ref_node.add(new_node)
 
    elif operation == 'count':
        if tree is None:
            print('Tree is empty.')
        else:
            count = tree.count_leaf_nodes()
            print('Number of leaf 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_leaf_nodes is called on the tree to calculate the number of leaf nodes in the tree.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
Runtime Test Cases
Case 1:
Menu (this assumes no duplicate keys)
add <data> at root
add <data> below <data>
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 1
What would you like to do? count
Number of leaf nodes: 2
What would you like to do? quit
 
Case 2:
Menu (this assumes no duplicate keys)
add <data> at root
add <data> below <data>
count
quit
What would you like to do? add 2 at root
What would you like to do? add 7 below 2
What would you like to do? add 8 below 7
What would you like to do? add 9 below 8
What would you like to do? count
Number of leaf nodes: 1
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.

Take Python Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.