# Iterative program to count leaf nodes in a Binary Tree

Given a binary tree, count leaves in the tree without using recursion. A node is a leaf node if both left and right children of it are NULL.

```  Example Tree Leaves count for the above tree is 3.```

The idea is to use level order traversal. During traversal, if we find a node whose left and right children are NULL, we increment count.

## C++

 `// C++ program to count leaf nodes in a Binary Tree ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree Node has data, pointer to left ` `   ``child  and a pointer to right child */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left, *right; ` `}; ` ` `  `/* Function to get the count of leaf Nodes in ` `   ``a binary tree*/` `unsigned ``int` `getLeafCount(``struct` `Node* node) ` `{ ` `    ``// If tree is empty ` `    ``if` `(!node) ` `        ``return` `0; ` ` `  `    ``// Initialize empty queue. ` `    ``queue q; ` ` `  `    ``// Do level order traversal starting from root ` `    ``int` `count = 0; ``// Initialize count of leaves ` `    ``q.push(node); ` `    ``while` `(!q.empty()) ` `    ``{ ` `        ``struct` `Node *temp = q.front(); ` `        ``q.pop(); ` ` `  `        ``if` `(temp->left != NULL) ` `            ``q.push(temp->left); ` `        ``if` `(temp->right != NULL) ` `            ``q.push(temp->right); ` `        ``if` `(temp->left == NULL && temp->right == NULL) ` `            ``count++; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `/* Helper function that allocates a new Node with the ` `   ``given data and NULL left and right pointers. */` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* node = ``new` `Node; ` `    ``node->data = data; ` `    ``node->left = node->right = NULL; ` `    ``return` `(node); ` `} ` ` `  `/* Driver program to test above functions*/` `int` `main() ` `{ ` `    ``/*   1 ` `        ``/  ` `      ``2     3 ` `     ``/ ` `    ``4   5 ` `    ``Let us create Binary Tree shown in  ` `    ``above example */` ` `  `    ``struct` `Node *root = newNode(1); ` `    ``root->left        = newNode(2); ` `    ``root->right       = newNode(3); ` `    ``root->left->left  = newNode(4); ` `    ``root->left->right = newNode(5); ` ` `  `    ``/* get leaf count of the above created tree */` `    ``cout << getLeafCount(root); ` ` `  `    ``return` `0; ` `} `

## Python3

 `# Python3 program to count leaf nodes  ` `# in a Binary Tree  ` `from` `queue ``import` `Queue  ` ` `  `# Helper function that allocates a new  ` `# Node with the given data and None  ` `# left and right pointers.  ` `class` `newNode: ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data  ` `        ``self``.left ``=` `self``.right ``=` `None` `         `  `# Function to get the count of leaf  ` `# Nodes in a binary tree ` `def` `getLeafCount(node): ` `     `  `    ``# If tree is empty  ` `    ``if` `(``not` `node): ` `        ``return` `0` ` `  `    ``# Initialize empty queue.  ` `    ``q ``=` `Queue() ` ` `  `    ``# Do level order traversal  ` `    ``# starting from root  ` `    ``count ``=` `0` `# Initialize count of leaves  ` `    ``q.put(node)  ` `    ``while` `(``not` `q.empty()): ` `        ``temp ``=` `q.queue[``0``]  ` `        ``q.get() ` ` `  `        ``if` `(temp.left !``=` `None``): ` `            ``q.put(temp.left)  ` `        ``if` `(temp.right !``=` `None``): ` `            ``q.put(temp.right)  ` `        ``if` `(temp.left ``=``=` `None` `and` `            ``temp.right ``=``=` `None``):  ` `            ``count ``+``=` `1` `    ``return` `count ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `'__main__'``: ` `     `  `    ``# 1  ` `    ``# /   ` `    ``# 2 3  ` `    ``# /   ` `    ``# 4 5  ` `    ``# Let us create Binary Tree shown  ` `    ``# in above example  ` `    ``root ``=` `newNode(``1``)  ` `    ``root.left ``=` `newNode(``2``)  ` `    ``root.right ``=` `newNode(``3``)  ` `    ``root.left.left ``=` `newNode(``4``)  ` `    ``root.left.right ``=` `newNode(``5``)  ` ` `  `    ``# get leaf count of the above  ` `    ``# created tree  ` `    ``print``(getLeafCount(root)) ` ` `  `# This code is contributed by PranchalK `

Output:

``` 3
```

Time Complexity: O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Tree Ola Cabs Ola Cabs Tree

code

load comments