Count Leaves in Binary Tree

Problem

Given a Binary Tree of size N, You have to count leaves in it. For example, there are two leaves in following tree.

     1
    / \
  10   39
 /
5

Examples:

Example 1:

Input:
Given Tree is 
               4
             /   \
            8     10
           /     /   \
          7     5     1
         /
        3 
Output:
3
Explanation: 
Three leaves are 3 , 5 and 1.

Your task:

You don't have to take input. Complete the function countLeaves() that takes root node of the given tree as parameter and returns the count of leaves in tree. The printing is done by the driver code.

Constraints:

• $1<=N<=10^4$

Solution

Python

def countLeaves(root):
    q = []
    q.append(root)
    count = 0
    while(len(q) > 0):
        temp = q.pop(0)
        if(temp.left is None and temp.right is None):
            count += 1
        if(temp.left is not None):
            q.append(temp.left)
        if(temp.right is not None):
            q.append(temp.right)
    return count

Java

int countLeaves(Node node) {
    Queue<Node> q = new LinkedList<Node>();
    q.add(node);
    int count = 0;
    while(!q.isEmpty()){
        Node temp = q.poll();
        if(temp.left == null && temp.right == null) count++;
        if(temp.left != null) q.add(temp.left);
        if(temp.right != null) q.add(temp.right);
    }
    return count; 
}

C++

int countLeaves(Node* root) {
    queue<Node*> q;
    q.push(root);
    int count = 0;
    while(!q.empty()){
        Node* temp = q.front();
        q.pop();
        if(temp->left == NULL && temp->right == NULL)
            count++;
        if(temp->left) q.push(temp->left);
        if(temp->right) q.push(temp->right);
    }
    return count;
}

C

int countLeaves(struct Node* root) {
    struct Node** queue = (struct Node**) malloc(1000 * sizeof(struct Node*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    int count = 0;
    while (front < rear) {
        struct Node* temp = queue[front++];
        if (temp->left == NULL && temp->right == NULL)
            count++;
        if (temp->left)
            queue[rear++] = temp->left;
        if (temp->right)
            queue[rear++] = temp->right;
    }
    free(queue);
    return count;
}