HomePythonPython Program to Count Leaf Nodes in a Tree

Python Program to Count Leaf Nodes in a Tree

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

Leave A Reply

Your email address will not be published. Required fields are marked *

You May Also Like

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...
This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...
This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...