Given a Binary Tree. The task is to write a program to find the product of all of the nodes of the given binary tree.
In the above binary tree,
Product = 15*10*8*12*20*16*25 = 115200000
The idea is to recursively:
- Find the product of the left subtree.
- Find the product of the right subtree.
- Multiply the product of left and right subtrees with the current node’s data and return.
Below is the implementation of the above approach:
C++
// Program to print product of all// the nodes of a binary tree#include <iostream>using namespace std;// Binary Tree Nodestruct Node { int key; Node *left, *right;};/* utility that allocates a new Node with the given key */Node* newNode(int key){ Node* node = new Node; node->key = key; node->left = node->right = NULL; return (node);}// Function to find product of// all the nodesint productBT(Node* root){ if (root == NULL) return 1; return (root->key * productBT(root->left) * productBT(root->right));}// Driver Codeint main(){ // Binary Tree is: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ // 8 Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); int prod = productBT(root); cout << "Product of all the nodes is: " << prod << endl; return 0;} |
Java
// Java Program to print product of all// the nodes of a binary tree import java.util.*;class solution{// Binary Tree Nodestatic class Node { int key; Node left, right;};/* utility that allocates a new Node with the given key */static Node newNode(int key){ Node node = new Node(); node.key = key; node.left = node.right = null; return (node);}// Function to find product of// all the nodesstatic int productBT(Node root){ if (root == null) return 1; return (root.key * productBT(root.left) * productBT(root.right));}// Driver Codepublic static void main(String args[]){ // Binary Tree is: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ // 8 Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); int prod = productBT(root); System.out.println( "Product of all the nodes is: "+prod);}}//contributed by Arnab Kundu |
Python3
# Python3 Program to print product of # all the nodes of a binary tree # Binary Tree Node """ utility that allocates a new Node with the given key """class newNode: # Construct to create a new node def __init__(self, key): self.key = key self.left = None self.right = None # Function to find product of # all the nodes def productBT( root) : if (root == None): return 1 return (root.key * productBT(root.left) * productBT(root.right)) # Driver Code if __name__ == '__main__': # Binary Tree is: # 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # \ # 8 root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.left = newNode(6) root.right.right = newNode(7) root.right.left.right = newNode(8) prod = productBT(root) print("Product of all the nodes is:", prod) # This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# Program to print product of all// the nodes of a binary tree using System;class GFG{ // Binary Tree Node class Node { public int key; public Node left, right; }; /* utility that allocates a new Node with the given key */ static Node newNode(int key) { Node node = new Node(); node.key = key; node.left = node.right = null; return (node); } // Function to find product of // all the nodes static int productBT(Node root) { if (root == null) return 1; return (root.key * productBT(root.left) * productBT(root.right)); } // Driver Code public static void Main() { // Binary Tree is: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ // 8 Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); int prod = productBT(root); Console.WriteLine( "Product of all " + "the nodes is: " + prod); }}/* This code is contributed PrinciRaj1992 */ |
Javascript
<script>// javascript Program to print product of all// the nodes of a binary tree // Binary Tree Nodeclass Node { constructor(val) { this.key = val; this.left = null; this.right = null; }}/* utility that allocates a new Node with the given key */function newNode(key){ var node = new Node(); node.key = key; node.left = node.right = null; return (node);}// Function to find product of// all the nodesfunction productBT(root){ if (root == null) return 1; return (root.key * productBT(root.left) * productBT(root.right));}// Driver Code // Binary Tree is: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ // 8 var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); var prod = productBT(root); document.write( "Product of all the nodes is: "+prod);// This code contributed by gauravrajput1 </script> |
Javascript
<script>// javascript Program to print product of all// the nodes of a binary tree // Binary Tree Nodeclass Node { constructor(val) { this.key = val; this.left = null; this.right = null; }}/* utility that allocates a new Node with the given key */function newNode(key){ var node = new Node(); node.key = key; node.left = node.right = null; return (node);}// Function to find product of// all the nodesfunction productBT(root){ if (root == null) return 1; return (root.key * productBT(root.left) * productBT(root.right));}// Driver Code // Binary Tree is: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ // 8 var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); var prod = productBT(root); document.write( "Product of all the nodes is: "+prod);// This code contributed by umadevi9616 </script> |
Output
Product of all the nodes is: 40320
Complexity Analysis
- Time complexity : O(n)
- As we are traversing the tree only once.
- Auxiliary Complexity: O(h)
- Here h is the height of the tree. The extra space is used in recursion call stack. In the worst case(when the 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!
