Given a Binary tree. The task is to find and print the product and sum of all internal nodes (non-leaf nodes) in the tree.
In the above tree, only two nodes 1 and 2 are non-leaf nodes.
Therefore, product of non-leaf nodes = 1 * 2 = 2.
And sum of non-leaf nodes = 1 + 2 =3.
Examples:
Input :
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Output : Product = 36, Sum = 12
Non-leaf nodes are: 1, 2, 3, 6
Approach:
The idea is to traverse the tree in any fashion and check if the current node is a non-leaf node or not. Take two variables product and sum to store the product and sum of non-leaf nodes respectively. If the current node is a non-leaf node then multiply the node’s data to the variable product used to store the products of non-leaf nodes and add the node’s data to the variable sum used to store the sum of non-leaf nodes.
Algorithm:
- Create a function called newNode that takes an integer parameter, and data, and returns a new node with null left and right pointers. It gives back the newly made node.
- With an integer variable named a, define the static class Int.
- Create the function findProductSum and define its three arguments: the root node, prod, and sum, two Int objects. This function calculates the product and sum of the binary tree’s non-leaf nodes. It carries out the subsequent actions:
- Return whether either the root node or the root node’s left and right child nodes are null.
- Multiply the product by the node’s data, then add the node’s data to the sum if the root node has at least one non-null child.
- Recursively call the findProductSum function for the left child of the root node.
- Recursively call the findProductSum function for the right child of the root node.
Below is the implementation of the above idea:
C++
// CPP program to find product and sum of// non-leaf nodes in a binary tree#include <bits/stdc++.h>using namespace std;/* A binary tree node has data, pointer to left child and a pointer to right child */struct Node { int data; struct Node* left; struct Node* right;};/* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct Node* newNode(int data){ struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);}// Computes the product of non-leaf // nodes in a treevoid findProductSum(struct Node* root, int& prod, int& sum){ // Base cases if (root == NULL || (root->left == NULL && root->right == NULL)) return; // if current node is non-leaf, // calculate product and sum if (root->left != NULL || root->right != NULL) { prod *= root->data; sum += root->data; } // If root is Not NULL and its one of its // child is also not NULL findProductSum(root->left, prod, sum); findProductSum(root->right, prod, sum);}// Driver Codeint main(){ // Binary Tree struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); int prod = 1; int sum = 0; findProductSum(root, prod, sum); cout <<"Product = "<<prod<<" , Sum = "<<sum; return 0;} |
Java
// Java program to find product and sum of // non-leaf nodes in a binary tree class GFG{/* A binary tree node has data, pointer to left child and a pointer to right child */static class Node { int data; Node left; Node right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } //int classstatic class Int{ int a;}// Computes the product of non-leaf // nodes in a tree static void findProductSum(Node root, Int prod, Int sum) { // Base cases if (root == null || (root.left == null && root.right == null)) return; // if current node is non-leaf, // calculate product and sum if (root.left != null || root.right != null) { prod.a *= root.data; sum.a += root.data; } // If root is Not null and its one of its // child is also not null findProductSum(root.left, prod, sum); findProductSum(root.right, prod, sum); } // Driver Code public static void main(String args[]){ // Binary Tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); Int prod = new Int();prod.a = 1; Int sum = new Int(); sum.a = 0; findProductSum(root, prod, sum); System.out.print("Product = " + prod.a + " , Sum = " + sum.a); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find product and sum # of non-leaf nodes in a binary tree# Helper function that allocates a new # node with the given data and None # left and right pointers. class newNode: # Construct to create a new node def __init__(self, key): self.data = key self.left = None self.right = None# Computes the product of non-leaf # nodes in a tree class new: def findProductSum(sf,root) : # Base cases if (root == None or (root.left == None and root.right == None)) : return # if current node is non-leaf, # calculate product and sum if (root.left != None or root.right != None) : sf.prod *= root.data sf.sum += root.data # If root is Not None and its one # of its child is also not None sf.findProductSum(root.left) sf.findProductSum(root.right) def main(sf): root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) sf.prod = 1 sf.sum = 0 sf.findProductSum(root) print("Product =", sf.prod, ", Sum =", sf.sum) # Driver Code if __name__ == '__main__': x = new() x.main()# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to find product and sum of // non-leaf nodes in a binary tree using System; class GFG{/* A binary tree node has data, pointer to left child and a pointer to right child */public class Node { public int data; public Node left; public Node right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // int classpublic class Int{ public int a;}// Computes the product of non-leaf // nodes in a tree static void findProductSum(Node root, Int prod, Int sum) { // Base cases if (root == null || (root.left == null && root.right == null)) return; // if current node is non-leaf, // calculate product and sum if (root.left != null || root.right != null) { prod.a *= root.data; sum.a += root.data; } // If root is Not null and its one of its // child is also not null findProductSum(root.left, prod, sum); findProductSum(root.right, prod, sum); } // Driver Code public static void Main(String []args){ // Binary Tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); Int prod = new Int();prod.a = 1; Int sum = new Int(); sum.a = 0; findProductSum(root, prod, sum); Console.Write("Product = " + prod.a + " , Sum = " + sum.a); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to find product and sum of // non-leaf nodes in a binary tree /* A binary tree node has data, pointer to left child and a pointer to right child */class Node { constructor() { this.data = 0; this.left = null; this.right = null; }}/* Helper function that allocates a new node with the given data and null left and right pointers. */function newNode(data) { var node = new Node(); node.data = data; node.left = node.right = null; return (node); } //var class class Int{constructor(){ this.a = 0; }}// Computes the product of non-leaf // nodes in a tree function findProductSum(root, prod, sum) { // Base cases if (root == null || (root.left == null && root.right == null)) return; // if current node is non-leaf, // calculate product and sum if (root.left != null || root.right != null) { prod.a *= root.data; sum.a += root.data; } // If root is Not null and its one of its // child is also not null findProductSum(root.left, prod, sum); findProductSum(root.right, prod, sum); } // Driver Code // Binary Tree root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); var prod = new Int(); prod.a = 1; var sum = new Int(); sum.a = 0; findProductSum(root, prod, sum); document.write("Product = " + prod.a + " , Sum = " + sum.a); // This code contributed by aashish1995 </script> |
Output
Product = 2 , Sum = 3
Complexity Analysis:
- Time Complexity: O(N)
- As we are visiting every node just once.
- Auxiliary Space: O(h)
- Here h is the height of the tree and extra space is used in recursion call stack. In the worst case(when tree is skewed) this can go upto O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
