Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

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
}
leaf nodes in a binary tree

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





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com (2015-2018), Some rights reserved.