Home » Data Structure

Find the number of leaf nodes in a Binary Tree | Data Structure

The article describes to find number of leaf nodes in a binary tree (C++ implementation). Submitted by Radib Kar, on October 05, 2018

Algorithm:

One of the popular traversal techniques to solve this kind of problems is level order tree traversal (Read: Level Order Traversal on a Binary Tree) where we use the concept of BFS.

The basic idea to solve the problem is:

1. Do a level order traversal and check whether the processed node has its left and right child both NULL.
2. If the processed node has its left and right child both NULL, it’s a leaf node.
3. Increase leaf node count

Pseudocode:

struct BT{              // tree node type
	int data;           //value
	struct BT *left;    //pointer to left child
	struct BT *right;   //pointer to right child
};


int noofleafnodes(struct BT *root){ // root of the tree
	// BT refers to node of tree (datatype for the node);
	struct BT *temp;                
	struct Queue *q=Creat_queue();  //creating a queue
	int count=0;
	if(!root)   //root is null
	return;
	//**using level oder search**
	EnQueue(q,root); // Enqueue the root in the queue
		
	while(!emptyQueue(q)){
		temp=DeQueue(q);  //Dequeue
		// processing the node and checking whether both child nodes are NULL or not 
		if(!temp->left && !temp->right) 
			//increase no of leaves count if both child nodes are NULL (ensures it's a leaf  node)
			count++;           
		else{
			if(temp->left)
				EnQueue(q,temp->left); // if left child exists EnQueue
			if(temp->right)
				EnQueue(q,temp->right); // if right child exists EnQueue
		}
	}
	DeleteQueue(q);
	return count; // return no of leaf nodes
}

Image source: wikipedia

Example:

The leaf nodes in the above tree is 2, 5, 11, 4

C++ implementation:

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

class tree{    // tree node is defined
	public:
	int data;
	tree *left;
	tree *right;
};

int noofleafnodes( tree *root){
	queue<tree*> q;  // using stl
	tree* temp;
	int count=0;
	q.push(root);
	while(!q.empty()){
		temp=q.front();
		q.pop();
		//process node and check wheather leaf node or not
		if(!temp->left && !temp->right){            
			count++;
			cout<<temp->data<<" ";
		}
		if(temp->left)
			q.push(temp->left); //EnQueue
		if(temp->right)
			q.push(temp->right); //EnQueue
	}
	cout<<endl;
	return count;
}
tree* newnode(int data)  // creating new node
{ 
    tree* node = (tree*)malloc(sizeof(tree)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return(node); 
} 
  

int main() 
{ 
    //**same tree is builted as shown in example**
	int c;
    tree *root=newnode(2); 
    root->left= newnode(7); 
    root->right= newnode(5); 
    root->right->right=newnode(9);
    root->right->right->left=newnode(4);
    root->left->left=newnode(2); 
    root->left->right=newnode(6);
    root->left->right->left=newnode(5);
    root->left->right->right=newnode(11);
  
    cout<<"printing the leaf nodes......"<<endl; 
    c=noofleafnodes(root);
	cout<<"no of leaf nodes is : "<<c<<endl;	
  
    return 0; 
} 

Output

printing the leaf nodes......
2 5 11 4
no of leaf nodes is : 4