Given a Binary Tree consisting of N nodes, the task is to replace each node of the tree with the product of all the remaining nodes.
Examples:
Input:
1
/ \
2 3
/ \
4 5
Output:
120
/ \
60 40
/ \
30 24Input:
2
/ \
2 3
Output:
6
/ \
6 4
Approach: The given problem can be solved by first calculating the product of all the nodes in the given Tree and then perform any tree traversal on the given tree and update each node by the value (P/(root->values). Follow the steps below to solve the problem:
- Find the product of all nodes of the binary tree using the Preorder Traversal and store it in a variable say P.
- Define a function, say updateTree(root, P), and perform the following steps:
- If the value of root is NULL, then return from the function.
- Update the current value of the root node to the value (P/root->value).
- Recursively call for the left and the right subtree as updateTree(root->left, P) and updateTree(root->right, P).
- After completing the above steps, print the Inorder Traversal of the modified tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A Tree nodeclass Node {public: int data; Node *left, *right; // Constructor Node(int data) { this->data = data; left = NULL; right = NULL; }};// Function to create a new node in// the given TreeNode* newNode(int value){ Node* temp = new Node(value); return (temp);}// Function to find the product of// all the nodes in the given Treeint findProduct(Node* root){ // Base Case if (root == NULL) return 1; // Recursively Call for the left // and the right subtree return (root->data * findProduct(root->left) * findProduct(root->right));}// Function to perform the Inorder// traversal of the given treevoid display(Node* root){ // Base Case if (root == NULL) return; // Recursively call for the // left subtree display(root->left); // Print the value cout << root->data << " "; // Recursively call for the // right subtree display(root->right);}// Function to convert the given tree// to the multiplication treevoid convertTree(int product, Node* root){ // Base Case if (root == NULL) return; // Divide the total product by // the root's data root->data = product / (root->data); // Go to the left subtree convertTree(product, root->left); // Go to the right subtree convertTree(product, root->right);}// Driver Codeint main(){ // Given Binary Tree Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->right->left = newNode(4); root->right->right = newNode(5); cout << "Inorder Traversal of " << "given Tree:\n"; // Print the tree traversal display(root); int product = findProduct(root); cout << "\nInorder Traversal of " << "given Tree:\n"; // Function Call convertTree(product, root); // Print the tree traversal display(root); return 0;} |
Python3
# Python3 program for the above approach# A Tree nodeclass Node: def __init__(self, d): self.data = d self.left = None self.right = None# Function to find the product of# all the nodes in the given Treedef findProduct(root): # Base Case if (root == None): return 1 # Recursively Call for the left # and the right subtree return (root.data * findProduct(root.left) * findProduct(root.right))# Function to perform the Inorder# traversal of the given treedef display(root): # Base Case if (root == None): return # Recursively call for the # left subtree display(root.left) # Print the value print(root.data, end = " ") # Recursively call for the # right subtree display(root.right)# Function to convert the given tree# to the multiplication treedef convertTree(product, root): # Base Case if (root == None): return # Divide the total product by # the root's data root.data = product // (root.data) # Go to the left subtree convertTree(product, root.left) # Go to the right subtree convertTree(product, root.right)# Driver Codeif __name__ == '__main__': # Given Binary Tree root = Node(1) root.left = Node(2) root.right = Node(3) root.right.left = Node(4) root.right.right = Node(5) print("Inorder Traversal of given Tree: ") # Print the tree traversal display(root) product = findProduct(root) print("\nInorder Traversal of given Tree:") # Function Call convertTree(product, root) # Print the tree traversal display(root)# This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachpublic class GFG { // TreeNode class static class Node { public int data; public Node left, right; }; static Node newNode(int key) { Node temp = new Node(); temp.data = key; temp.left = temp.right = null; return temp; } // Function to find the product of // all the nodes in the given Tree static int findProduct(Node root) { // Base Case if (root == null) return 1; // Recursively Call for the left // and the right subtree return (root.data * findProduct(root.left) * findProduct(root.right)); } // Function to perform the Inorder // traversal of the given tree static void display(Node root) { // Base Case if (root == null) return; // Recursively call for the // left subtree display(root.left); // Print the value System.out.print(root.data + " "); // Recursively call for the // right subtree display(root.right); } // Function to convert the given tree // to the multiplication tree static void convertTree(int product, Node root) { // Base Case if (root == null) return; // Divide the total product by // the root's data root.data = product / (root.data); // Go to the left subtree convertTree(product, root.left); // Go to the right subtree convertTree(product, root.right); } // Driver code public static void main(String[] args) { // Given Binary Tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(5); System.out.println("Inorder Traversal of " + "given Tree:"); // Print the tree traversal display(root); int product = findProduct(root); System.out.println("\nInorder Traversal of " + "given Tree:"); // Function Call convertTree(product, root); // Print the tree traversal display(root); }}// This code is contributed by abhinavjain194 |
C#
// C# program for the above approachusing System;public class GFG { // TreeNode class class Node { public int data; public Node left, right; }; static Node newNode(int key) { Node temp = new Node(); temp.data = key; temp.left = temp.right = null; return temp; } // Function to find the product of // all the nodes in the given Tree static int findProduct(Node root) { // Base Case if (root == null) return 1; // Recursively Call for the left // and the right subtree return (root.data * findProduct(root.left) * findProduct(root.right)); } // Function to perform the Inorder // traversal of the given tree static void display(Node root) { // Base Case if (root == null) return; // Recursively call for the // left subtree display(root.left); // Print the value Console.Write(root.data + " "); // Recursively call for the // right subtree display(root.right); } // Function to convert the given tree // to the multiplication tree static void convertTree(int product, Node root) { // Base Case if (root == null) return; // Divide the total product by // the root's data root.data = product / (root.data); // Go to the left subtree convertTree(product, root.left); // Go to the right subtree convertTree(product, root.right); } // Driver code public static void Main(String[] args) { // Given Binary Tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(5); Console.WriteLine("Inorder Traversal of " + "given Tree:"); // Print the tree traversal display(root); int product = findProduct(root); Console.WriteLine("\nInorder Traversal of " + "given Tree:"); // Function Call convertTree(product, root); // Print the tree traversal display(root); }}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // TreeNode class class Node { constructor() { this.data = 0; this.left = null; this.right = null; } } function newNode(key) { var temp = new Node(); temp.data = key; temp.left = temp.right = null; return temp; } // Function to find the product of // all the nodes in the given Tree function findProduct(root) { // Base Case if (root == null) return 1; // Recursively Call for the left // and the right subtree return root.data * findProduct(root.left) * findProduct(root.right); } // Function to perform the Inorder // traversal of the given tree function display(root) { // Base Case if (root == null) return; // Recursively call for the // left subtree display(root.left); // Print the value document.write(root.data + " "); // Recursively call for the // right subtree display(root.right); } // Function to convert the given tree // to the multiplication tree function convertTree(product, root) { // Base Case if (root == null) return; // Divide the total product by // the root's data root.data = parseInt(product / root.data); // Go to the left subtree convertTree(product, root.left); // Go to the right subtree convertTree(product, root.right); } // Driver code // Given Binary Tree var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(5); document.write("Inorder Traversal of " + "given Tree: <br>"); // Print the tree traversal display(root); var product = findProduct(root); document.write("<br>Inorder Traversal of " + "given Tree:<br>"); // Function Call convertTree(product, root); // Print the tree traversal display(root); // This code is contributed by rdtank. </script> |
Output:
Inorder Traversal of given Tree: 2 1 4 3 5 Inorder Traversal of given Tree: 60 120 30 40 24
Time Complexity: O(N)
Auxiliary Space: 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!
