Count of leaf nodes

You are given a non-empty binary tree. You need to find out the number of leaf nodes present in the tree. Leaf nodes are those nodes which do not have any children.

In the tree above, there are 4 leaf nodes with values 1, 4, 7, 13 respectively.

Algorithm

We can solve the problem recursively. If the current node is a null pointer, we return 0. If the current node is a leaf node, that is it’s left and right child are null pointers, we return 1. Else, we return the sum of recursive calls on left and right child of the current node.

For a better understanding, have a look on the code below.

#include <bits/stdc++.h>
using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int getCountOfLeafNodes(Node* node){
    if(node == nullptr){
        return 0;
    }
    if(node->left == nullptr && node->right == nullptr){
        return 1;
    }
    return getCountOfLeafNodes(node->left) + getCountOfLeafNodes(node->right);
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    cout<<"Total number of leaf nodes are: "<<getCountOfLeafNodes(root)<<endl;
    return 0;
}

Also, take a look at another popular interview problem Minimum unsorted subarray.

One comment

Leave a Reply

Your email address will not be published.