Given a binary tree, write a program to count the number of leaf nodes. A leaf node is a node which does not have left and right children.

For example consider the following binary tree.

For example consider the following binary tree.

It has 3 leaf nodes namely **1**, **4** and **7**.

The solution is simple. The number of leaf nodes of a binary tree rooted at R is the sum of leaf nodes in the left and sub trees. Using this property we can devise a simple recursive solution.

This can also be solved using iterative solution by traversing the binary tree using BFS (Breadth First Search) traversal.

The following C++ program shows both recursive and iterative implementations.