Python program to count leaf nodes in a binary tree without using recursion.














































Python program to count leaf nodes in a binary tree without using recursion.



Description:

This python article is about counting leaf nodes in a binary tree. A tree is a type of data structure with a hierarchical structure. It contains parent nodes as well as child nodes.  Binary Tree is a tree with following set of rules:

Each node can have either 0, 1 or 2 child nodes.
Each child node can have only 1 parent node.

Leaf nodes are nodes that do not have any child nodes. In our program we, first create a class 'Node' in it we create a constructor to create instance of class Node. After that we, create a function 'insert' to insert new nodes in our binary tree. When a node inserted is less than its parent node then it is placed as left child of the parent node and when the inserted node is greater than parent node it is placed as the right child of the parent node. For achieving this we compare the inserted node and its parent node in the 'insert' function itself. Then, we create a 'PrintTree' function to print the tree we'll create using the insert method. Out of the class Node, we create a function 'getLeafCount' to count the number of leaf nodes.

In our program, we then create nodes using the insert method and by passing values of the nodes to be inserted. After that we call the getLeafCount function to count the leaf nodes in our tree.

Program:

#! /usr/bin/env python3 class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Compare the new value with the parent node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Function to get the count of leaf nodes in binary tree def getLeafCount(node): if node is None: return 0 if(node.left is None and node.right is None): return 1 else: return (getLeafCount(node.left) + getLeafCount(node.right)) # Use the insert method to add nodes root = Node(14) root.insert(2) root.insert(1) root.insert(3) root.insert(4) root.insert(25) root.PrintTree() print ("Leaf count of the tree is ",getLeafCount(root))

Output:

Comments