This is a Python program to count the number of leaf nodes in a tree.
The program creates a tree and counts the number of leaf nodes in the tree.
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.
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
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.
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.
- Check Information Technology Books
- Practice Programming MCQs
- Apply for Python Internship
- Apply for Programming Internship
- Check Python Books
