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.