Given a binary tree of N nodes, the task is to find the maximum product of the elements of any path in the binary tree.
Note: A path starts from the root and ends at any leaf in the tree.
Examples:
Input:
4
/ \
2 8
/ \ / \
2 1 3 4Output: 128
Explanation: Path in the given tree goes like {4, 8, 4} which gives the max score of 4 x 8 x 4 = 128.Input:
10
/ \
7 5
\
1Output: 70
Explanation: The path {10, 7} gives a score of 70 which is the maximum possible.
Approach: The idea to solve the problem is by using DFS traversal of a tree using recursion.
For every node recursively find the maximum product of left subtree and right subtree of that node and return the product of that value with the node’s data.
Follow the steps mentioned below to solve the problem
- As the base Condition. If the root is NULL, simply return 1.
- Call the recursive function for the left and right subtrees to get the maximum product from both the subtrees.
- Return the value of the current node multiplied by the maximum product out of the left and right subtree as the answer of the current recursion.
Below is the implementation of the above approach.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Structure of a tree Nodestruct Node { int data; Node* left; Node* right; Node(int val) { this->data = val; }};// Utility function to create a new Tree Nodelong long findMaxScore(Node* root){ // Base Condition if (root == 0) return 1; // max product path = root->data // multiplied by max of // max_product_path of left subtree // and max_product_path // of right subtree return root->data * max(findMaxScore(root->left), findMaxScore(root->right));}// Driver Codeint main(){ Node* root = new Node(4); root->left = new Node(2); root->right = new Node(8); root->left->left = new Node(3); root->left->right = new Node(1); root->right->left = new Node(3); root->right->right = new Node(4); // Function call cout << findMaxScore(root) << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG{ // Structure of a tree Node public static class Node { int data; Node left; Node right; Node(int val) { this.data = val; } } // Utility function to create a new Tree Node public static long findMaxScore(Node root) { // Base Condition if (root == null) return 1; // Mmax product path = root.data // multiplied by max of // max_product_path of left subtree // and max_product_path // of right subtree return root.data * Math.max(findMaxScore(root.left), findMaxScore(root.right)); } // Driver Code public static void main(String[] args) { Node root = new Node(4); root.left = new Node(2); root.right = new Node(8); root.left.left = new Node(3); root.left.right = new Node(1); root.right.left = new Node(3); root.right.right = new Node(4); // Function call System.out.println(findMaxScore(root)); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach# Structure of a tree Nodeclass Node: def __init__(self,d): self.data = d self.left = None self.right = None# Utility function to create a new Tree Nodedef findMaxScore(root): # Base Condition if (root == None): return 1 # Mmax product path = root->data # multiplied by max of # max_product_path of left subtree # and max_product_path # of right subtree return root.data * max(findMaxScore(root.left),findMaxScore(root.right))# Driver Coderoot = Node(4)root.left = Node(2)root.right = Node(8)root.left.left = Node(3)root.left.right = Node(1)root.right.left = Node(3)root.right.right = Node(4)# Function callprint(findMaxScore(root))# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;class GFG{ // Structure of a tree Node public class Node { public int data; public Node left; public Node right; public Node(int val) { this.data = val; } } // Utility function to create a new Tree Node public static long findMaxScore(Node root) { // Base Condition if (root == null) return 1; // Mmax product path = root.data // multiplied by max of // max_product_path of left subtree // and max_product_path // of right subtree return root.data * Math.Max(findMaxScore(root.left), findMaxScore(root.right)); }// Driver Codepublic static void Main(){ Node root = new Node(4); root.left = new Node(2); root.right = new Node(8); root.left.left = new Node(3); root.left.right = new Node(1); root.right.left = new Node(3); root.right.right = new Node(4); // Function call Console.WriteLine(findMaxScore(root));}}// This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript code for the above approach // Structure of a tree Node class Node { constructor(d) { this.data = d; this.left = null; this.right = null; } }; // Utility function to create a new Tree Node function findMaxScore(root) { // Base Condition if (root == null) return 1; // Mmax product path = root->data // multiplied by max of // max_product_path of left subtree // and max_product_path // of right subtree return root.data * Math.max(findMaxScore(root.left), findMaxScore(root.right)); } // Driver Code let root = new Node(4); root.left = new Node(2); root.right = new Node(8); root.left.left = new Node(3); root.left.right = new Node(1); root.right.left = new Node(3); root.right.right = new Node(4); // Function call document.write(findMaxScore(root) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output
128
Time Complexity: O(N).
Auxiliary Space: O( Height of the tree)
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!
