Program to count leaf nodes in a binary tree

Problem

Count leaf nodes in a binary tree

Solution

Method 1 - Recursive
Here is the logic:

1. If node is NULL then return 0.
2. Else If left and right child nodes are NULL return 1.
3. Else recursively calculate leaf count of the tree using below formula.
   Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree

Here is the recursive solution:

int countLeaves(Node node){
  if( node == null )
    return 0;
  if( node.left == null && node.right == null ) {
    return 1;
  } else {
    return countLeaves(node.left) + countLeaves(node.right);
  }
}

Time complexity - O(n)

Method 2 - Iterative
Here we can use Queue. Idea is to use Level Order traversal.

int countLeaves(Node root)
{
  int count=0;
    if(root==null)
      return 0;

    Queue<Node> myqueue = new Queue<Node>();
    myqueue.push(root);

    while(!myqueue.empty())
    {
      Node temp;
       temp=myqueue.pop();//take the top element from the queue
      if(temp.left==null && temp.right==null)
       count++;
      if(temp.left!=null)
       myqueue.push(temp.left);
      if(temp.right!=null)
       myqueue.push(temp.right);
    }
  return count;
}

Time complexity - O(n)
Space Complexity - O(n)  for queue

Referenes

• http://www.geeksforgeeks.org/write-a-c-program-to-get-count-of-leaf-nodes-in-a-binary-tree/
• http://stackoverflow.com/questions/5949882/counting-number-of-leaf-nodes-in-binary-tree