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