This Python program counts the number of non-leaf nodes in a given tree data structure. A tree is a hierarchical structure where each node can have zero or more child nodes, and non-leaf nodes are those that have at least one child.
Given a tree, the program aims to count the number of non-leaf nodes present in the tree.
Python Program to Count Non Leaf Nodes in a Tree
class TreeNode: def __init__(self, value): self.value = value self.children =  def count_non_leaf_nodes(node): if not node: return 0 if not node.children: return 0 non_leaf_count = 1 # Initialize with 1 for the current non-leaf node for child in node.children: non_leaf_count += count_non_leaf_nodes(child) return non_leaf_count # Example tree structure # A # / \ # B C # / \ \ # D E F # Constructing the tree root = TreeNode('A') root.children = [TreeNode('B'), TreeNode('C')] root.children.children = [TreeNode('D'), TreeNode('E')] root.children.children = [TreeNode('F')] # Count non-leaf nodes result = count_non_leaf_nodes(root) print("Number of non-leaf nodes:", result)
How It Works
The program defines a
TreeNode class representing a node in the tree. Each node contains a value and a list of children nodes. The
count_non_leaf_nodes function recursively traverses the tree and counts the non-leaf nodes. If a node has no children, it’s not considered a non-leaf node. Otherwise, the function traverses each child node and accumulates the count. The count starts at 1 for the current non-leaf node.