by A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics and Binary Tree implementation.
Let’s have a look on basic class definition for Binary Tree.
class BinaryTree
{
public:
int m_data;
BinaryTree* m_left;
BinaryTree* m_right;
BinaryTree (int data);
BinaryTree (int data, BinaryTree* left, BinaryTree* right);
~BinaryTree ();
};
void print_binary_tree (BinaryTree* root)
{
cout << " " << root -> m_data;
if (root -> m_left)
print_binary_tree (root -> m_left);
if (root -> m_right)
print_binary_tree (root -> m_right);
}
void print_tree (BinaryTree* root)
{
cout << "Binary tree contents: ";
print_binary_tree (root);
cout << endl;
}
Count Leaf nodes in a Binary Tree
A node will be called a leaf node if that leaf has no children. This problem can be solved in multiple ways. In this article, we will see the two most efficient program to count the number of leaf nodes present in the Binary Tree.
Let’s look into an example to understand it better.
For the Binary tree mentioned in above image, Leaf nodes = 5
Count Leaf nodes in a Binary Tree using Iteration
In this method, we will count the number of leaf nodes using iterations. Let’s look into the algorithm to count the leaf node.
Algorithm
- If Binary Tree is empty return 0.
- Push root node into a Queue.
- While Queue is not empty
- dequeue the node from Queue.
- Enqueue the left and right child of the dequeued node if they are present in Queue.
- If dequeued node doesn’t has any children then increment the leaf_counter.
- return leaf_counter.
Few of the functions used below are explained in Generic Queue implementation. Refer those before going ahead.
Let’s look into the sample code for counting leaf nodes using iteration.
int get_number_of_leaves_using_iteration (BinaryTree* root)
{
if (!root)
return 0;
Queue q (10);
int count = 0;
BinaryTree* temp = NULL;
q.enqueue (root);
while (!q.isEmpty ())
{
temp = q.dequeue ();
if (temp -> m_left)
{
q.enqueue (temp -> m_left);
}
if (temp -> m_right)
{
q.enqueue (temp -> m_right);
}
if (!temp -> m_right && !temp -> m_left)
{
count++;
}
}
return count;
}
Count Leaf nodes in a Binary Tree using Recursion
In this method, we will count the number of leaf nodes using recursion. Let’s look into the algorithm to count the leaf nodes.
Algorithm
- If Binary Tree is empty return 0.
- if root node has no children then return 1.
- Call the recursive function with root left child and save function return value as leaf_left.
- Call the recursive function with root right child and save function return value as leaf_right.
- return (leaf_left + leaf_right).
Let’s look into the sample code for counting leaf nodes using recursion.
int get_number_of_leaves (BinaryTree* root)
{
if (!root)
return 0;
if (!root -> m_left && !root -> m_right)
return 1;
int max_left = get_number_of_leaves (root -> m_left);
int max_right = get_number_of_leaves (root -> m_right);
return (max_left + max_right);
}
Few of the functions used below are explained in Binary Tree Implementation. Refer those before going ahead.
Let’s define a main function to use above functions.
int main ()
{
BinaryTree* node1 = new BinaryTree (1);
BinaryTree* node2 = new BinaryTree (2);
BinaryTree* node3 = new BinaryTree (3);
BinaryTree* node4 = new BinaryTree (4);
BinaryTree* node5 = new BinaryTree (5);
BinaryTree* node6 = new BinaryTree (6);
BinaryTree* node7 = new BinaryTree (7);
BinaryTree* node8 = new BinaryTree (8);
BinaryTree* node9 = new BinaryTree (9);
BinaryTree* node10 = new BinaryTree (10);
/* Set node5 as root node */
BinaryTree* root = node5;
node5 -> m_left = node3;
node3 -> m_left = node2;
node3 -> m_right = node4;
node2 -> m_left = node1;
node5 -> m_right = node7;
node7 -> m_left = node6;
node7 -> m_right = node9;
node9 -> m_right = node10;
node9 -> m_left = node8;
print_tree (root);
cout << "Number of Leafs in Binary Tree: " << get_number_of_leaves (root) << endl;
cout << "Number of Leafs in Binary Tree: " << get_number_of_leaves_using_iteration (root) << endl;
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 3 2 1 4 7 6 9 8 10
Number of Leafs in Binary Tree: 5
Number of Leafs in Binary Tree: 5
