This python program calculates the number of leaf nodes in a given tree data structure.
Problem Statement
Given a tree, the task is to count the number of leaf nodes in the tree.
Python Program to Count Leaf Nodes in a Tree
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def count_leaf_nodes(node):
if not node.children:
return 1
else:
leaf_count = 0
for child in node.children:
leaf_count += count_leaf_nodes(child)
return leaf_count
# Example tree:
# 1
# / | \
# 2 3 4
# / \
# 5 6
root = TreeNode(1)
root.children = [TreeNode(2), TreeNode(3), TreeNode(4)]
root.children[0].children = [TreeNode(5), TreeNode(6)]
leaf_count = count_leaf_nodes(root)
print("Number of leaf nodes:", leaf_count)
How it Works
The program defines a TreeNode class that represents each node in the tree. Each node has a value and a list of children. The count_leaf_nodes function recursively traverses the tree. If a node has no children, it’s considered a leaf node and the function returns 1. If a node has children, the function recursively calls itself on each child and sums up the results to get the total number of leaf nodes.
Input/Output
