Find the product of all leaf nodes of a binary tree | faceprep

Program to find the product of all leaf nodes of a binary tree is discussed here. A leaf node is nothing but the terminal node, the node with no children. The algorithm to solve this problem is as below.

  • Start traversing the tree from the root node.
  • Check if every node is a leaf node or not.
  • If the node is a leaf node, then multiply the node with a variable temp_prod which is used to hold the product value of all the leaf nodes.

For example, consider the given tree

product of all leaf nodes in a tree

  • The leaf nodes in the above binary tree are 8, 5, 6 and 9.
  • The product of the leaf nodes  = 8*5*6*9 = 2160

Program to find the product of all leaf nodes of a binary tree

// C++ program to find the product of all leaf nodes of a binary tree

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

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

struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

void leafProduct(node* root, int& prod)
{
if (!root)
return;

if (!root->left && !root->right)
prod *= root->data;

leafProduct(root->left, prod);
leafProduct(root->right, prod);
}

void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

int main()
{
struct node *root = NULL;
int n;
int prod = 1;
cout << “\nEnter the number of edges : “;
cin >> n;
while(n–)
{
char lr;
int n1,n2;
cin >> n1 >> n2;
cin >>lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}

}
leafProduct(root,prod);
cout << “Product of the leaves : ” << prod << endl;
return 0;
}