Min-Max Product Tree of a given Binary Tree
Given a Binary Tree, the task is to convert the given Binary tree into Min-Max Product Tree and print the level-order sequence of the modified tree.
Min-Max Product Tree: A Min-Max Product Tree contains the product of the minimum and maximum values of its left and right subtrees at each node.
Note: For any node having only a single child, the value of that child node will be considered as both the minimum and the maximum.
Examples:
Input:
1
/ \
12 11
/ / \
3 4 13
\ /
15 5
Output:
45 9 60 3 225 25 15 5
Explanation:
Min-Max Product Tree:
45 (3 * 15)
/ \
( 3 * 3)9 60 (4 * 15)
/ / \
3 225 25 (5* 5)
\ /
15 5
Input:
5
/ \
21 77
/ \ \
61 16 16
\ /
10 3
/
23
Output:
231 610 48 61 230 9 529 3 23
Approach:
The idea is to use the post order traversal to traverse the left and right subtree recursively and extract the minimum and maximum. Store the product of minimum and maximum for every node in the Min-Max Product tree. Once, computed, compare the current node value with the current minimum and maximum and modify accordingly. Return the new minimum and maximum for the node at a higher level. Repeat this process for all nodes and finally, print the level order traversal of the Min-Max Product tree.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int data; struct Node *left, *right;};// Utility function to create// a new nodeNode* newNode(int key){ Node* temp = new Node; temp->data = key; temp->left = temp->right = NULL; return (temp);}// A minMax Structure for storing// minimum and maximum valuestruct minMax { int min; int max;};// Function to return min valueint min(minMax* a, minMax* b){ if (a != NULL && b != NULL) { return a->min < b->min ? a->min : b->min; } return a == NULL ? b->min : a->min;}// Function to return max valueint max(minMax* a, minMax* b){ if (a != NULL && b != NULL) { return a->max > b->max ? a->max : b->max; } return a == NULL ? b->max : a->max;}// Function to return min valueint min(int x, int y){ return x < y ? x : y;}// Function to return max valueint max(int x, int y){ return x > y ? x : y;}// Utility function to create// min-max product treeminMax* minMaxTreeUtil( Node* root){ // Base condition if (root == NULL) { return NULL; } minMax* var = new minMax; // Condition to check if // current node is leaf node if (root->left == NULL && root->right == NULL) { var->min = root->data; var->max = root->data; return var; } // Left recursive call minMax* left = minMaxTreeUtil(root->left); // Right recursive call minMax* right = minMaxTreeUtil(root->right); // Store Min var->min = min(left, right); // Store Max var->max = max(left, right); // Store current node data int currData = root->data; // Assign product of minimum // and maximum value root->data = var->min * var->max; // Again store min by considering // current node value var->min = min(var->min, currData); // Again store max by considering // current node value var->max = max(var->max, currData); return var;}void print(Node* root){ // Base Case if (root == NULL) return; // Create an empty queue for // level order traversal queue<Node*> q; // Enqueue Root and initialize // height q.push(root); while (q.empty() == false) { // nodeCount (queue size) // indicates number // of nodes at current level. int nodeCount = q.size(); // Dequeue all nodes of current // level and Enqueue all nodes // of next level while (nodeCount > 0) { Node* node = q.front(); cout << node->data << " "; q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); nodeCount--; } }}void minMaxProductTree(Node* root){ // Utility Function call minMaxTreeUtil(root); // Print tree print(root);}// Driver Codeint main(){ /* 10 / \ 48 3 / \ 11 37 / \ / \ 7 29 42 19 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(48); root->right = newNode(3); root->right->left = newNode(11); root->right->right = newNode(37); root->right->left->left = newNode(7); root->right->left->right = newNode(29); root->right->right->left = newNode(42); root->right->right->right = newNode(19); root->right->right->right->left = newNode(7); // Create Min Max Product Tree minMaxProductTree(root); return 0;} |
Java
// Java program for the// above approachimport java.util.*;// A Tree nodeclass Node { public int data; public Node left, right; public Node(int x) { data = x; left = null; right = null; }}// A minMax Structure for storing// minimum and maximum valueclass minMax { public int min, max; public minMax(int x, int y) { min = x; max = y; }}class GFG { // Function to return min value static int minm(minMax a, minMax b) { if (a != null && b != null) { if (a.min < b.min) return a.min; return b.min; } if (a == null) return b.min; return a.min; } // Function to return max value static int maxm(minMax a, minMax b) { if (a != null && b != null) { if (a.max > b.max) return a.max; return b.max; } if (a == null) return b.max; return a.max; } // Utility function to create // min-max product tree static minMax minMaxTreeUtil(Node root) { // Base condition if (root == null) return null; minMax var1 = new minMax(1000000000, -1000000000); // Condition to check if // current node is leaf node if (root.left == null && root.right == null) { var1.min = root.data; var1.max = root.data; return var1; } // Left recursive call minMax left = minMaxTreeUtil(root.left); // Right recursive call minMax right = minMaxTreeUtil(root.right); // Store Min var1.min = minm(left, right); // Store Max var1.max = maxm(left, right); // Store current node data int currData = root.data; // Assign product of minimum // and maximum value root.data = var1.min * var1.max; // Again store min by considering // current node value var1.min = Math.min(var1.min, currData); // Again store max by considering // current node value var1.max = Math.max(var1.max, currData); return var1; } static void printt(Node root) { // Base Case if (root == null) return; // Create an empty queue for // level order traversal ArrayList<Node> q = new ArrayList<Node>(); // Enqueue Root and initialize // height q.add(root); while (q.size() > 0) { // nodeCount (queue size) // indicates number // of nodes at current level. int nodeCount = q.size(); // Dequeue all nodes of current // level and Enqueue all nodes // of next level while (nodeCount > 0) { Node node = q.get(0); q.remove(0); System.out.print(node.data + " "); if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); nodeCount -= 1; } } } static void minMaxProductTree(Node root) { // Utility Function call minMaxTreeUtil(root); // Print tree printt(root); } // Driver Code public static void main(String[] args) { // /* 10 // / \ // 48 3 // / \ // 11 37 // / \ / \ // 7 29 42 19 // / // 7 // */ // Create Binary Tree as shown Node root = new Node(10); root.left = new Node(48); root.right = new Node(3); root.right.left = new Node(11); root.right.right = new Node(37); root.right.left.left = new Node(7); root.right.left.right = new Node(29); root.right.right.left = new Node(42); root.right.right.right = new Node(19); root.right.right.right.left = new Node(7); // Create Min Max Product Tree minMaxProductTree(root); }}// This code is contributed by phasing17 |
Python3
# Python3 program for the # above approachfrom collections import deque# A Tree nodeclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# A minMax Structure for storing# minimum and maximum valueclass minMax: def __init__(self, x, y): self.min = x self.max = y# Function to return min valuedef minm(a, b): if (a != None and b != None): if a.min < b.min: return a.min return b.min if a == None: return b.min return a.min# Function to return max valuedef maxm(a, b): if a != None and b != None: if a.max > b.max: return a.max return b.max if a == None: return b.max return a.max# Utility function to create# min-max product treedef minMaxTreeUtil(root): # Base condition if (root == None): return None var = minMax(10 ** 9, -10 ** 9) # Condition to check if # current node is leaf node if (root.left == None and root.right == None): var.min = root.data var.max = root.data return var # Left recursive call left= minMaxTreeUtil(root.left) # Right recursive call right= minMaxTreeUtil(root.right) # Store Min var.min = minm(left, right) # Store Max var.max = maxm(left, right) # Store current node data currData = root.data # Assign product of minimum # and maximum value root.data = var.min * var.max # Again store min by considering # current node value var.min = min(var.min, currData) # Again store max by considering # current node value var.max = max(var.max, currData) return vardef printt(root): # Base Case if (root == None): return # Create an empty queue for # level order traversal q = deque() # Enqueue Root and initialize # height q.append(root) while (len(q) > 0): # nodeCount (queue size) # indicates number # of nodes at current level. nodeCount = len(q) # Dequeue all nodes of current # level and Enqueue all nodes # of next level while (nodeCount > 0): node = q.popleft() print(node.data, end = " ") if (node.left != None): q.append(node.left) if (node.right != None): q.append(node.right) nodeCount -= 1def minMaxProductTree(root): # Utility Function call minMaxTreeUtil(root) # Print tree printt(root)# Driver Codeif __name__ == '__main__': # /* 10 # / \ # 48 3 # / \ # 11 37 # / \ / \ # 7 29 42 19 # / # 7 # */ # Create Binary Tree as shown root = Node(10) root.left = Node(48) root.right = Node(3) root.right.left = Node(11) root.right.right = Node(37) root.right.left.left = Node(7) root.right.left.right = Node(29) root.right.right.left = Node(42) root.right.right.right = Node(19) root.right.right.right.left = Node(7) # Create Min Max Product Tree minMaxProductTree(root)# This code is contributed by Mohit Kumar 29 |
C#
// C# program for the// above approachusing System;using System.Collections.Generic;// A Tree nodeclass Node { public int data; public Node left, right; public Node(int x) { data = x; left = null; right = null; }}// A minMax Structure for storing// minimum and maximum valueclass minMax { public int min, max; public minMax(int x, int y) { min = x; max = y; }}class GFG { // Function to return min value static int minm(minMax a, minMax b) { if (a != null && b != null) { if (a.min < b.min) return a.min; return b.min; } if (a == null) return b.min; return a.min; } // Function to return max value static int maxm(minMax a, minMax b) { if (a != null && b != null) { if (a.max > b.max) return a.max; return b.max; } if (a == null) return b.max; return a.max; } // Utility function to create // min-max product tree static minMax minMaxTreeUtil(Node root) { // Base condition if (root == null) return null; minMax var1 = new minMax(1000000000, -1000000000); // Condition to check if // current node is leaf node if (root.left == null && root.right == null) { var1.min = root.data; var1.max = root.data; return var1; } // Left recursive call minMax left = minMaxTreeUtil(root.left); // Right recursive call minMax right = minMaxTreeUtil(root.right); // Store Min var1.min = minm(left, right); // Store Max var1.max = maxm(left, right); // Store current node data int currData = root.data; // Assign product of minimum // and maximum value root.data = var1.min * var1.max; // Again store min by considering // current node value var1.min = Math.Min(var1.min, currData); // Again store max by considering // current node value var1.max = Math.Max(var1.max, currData); return var1; } static void printt(Node root) { // Base Case if (root == null) return; // Create an empty queue for // level order traversal List<Node> q = new List<Node>(); // Enqueue Root and initialize // height q.Add(root); while (q.Count > 0) { // nodeCount (queue size) // indicates number // of nodes at current level. int nodeCount = q.Count; // Dequeue all nodes of current // level and Enqueue all nodes // of next level while (nodeCount > 0) { Node node = q[0]; q.RemoveAt(0); Console.Write(node.data + " "); if (node.left != null) q.Add(node.left); if (node.right != null) q.Add(node.right); nodeCount -= 1; } } } static void minMaxProductTree(Node root) { // Utility Function call minMaxTreeUtil(root); // Print tree printt(root); } // Driver Code public static void Main(string[] args) { // /* 10 // / \ // 48 3 // / \ // 11 37 // / \ / \ // 7 29 42 19 // / // 7 // */ // Create Binary Tree as shown Node root = new Node(10); root.left = new Node(48); root.right = new Node(3); root.right.left = new Node(11); root.right.right = new Node(37); root.right.left.left = new Node(7); root.right.left.right = new Node(29); root.right.right.left = new Node(42); root.right.right.right = new Node(19); root.right.right.right.left = new Node(7); // Create Min Max Product Tree minMaxProductTree(root); }}// This code is contributed by phasing17 |
Javascript
// JS program for the // above approach// A Tree nodeclass Node{ constructor(x) { this.data = x this.left = null this.right = null }} // A minMax Structure for storing// minimum and maximum valueclass minMax{ constructor(x, y) { this.min = x this.max = y }}// Function to return min valuefunction minm(a, b){ if (a != null && b != null) { if (a.min < b.min) return a.min return b.min } if (a == null) return b.min return a.min}// Function to return max valuefunction maxm(a, b){ if (a != null && b != null) { if (a.max > b.max) return a.max return b.max } if (a == null) return b.max return a.max}// Utility function to create// min-max product treefunction minMaxTreeUtil(root){ // Base condition if (root == null) return null var var1 = new minMax(10 ** 9, - (10 ** 9)); // Condition to check if // current node is leaf node if (root.left == null && root.right == null) { var1.min = root.data var1.max = root.data return var1 } // Left recursive call left= minMaxTreeUtil(root.left) // Right recursive call right= minMaxTreeUtil(root.right) // Store Min var1.min = minm(left, right) // Store Max var1.max = maxm(left, right) // Store current node data currData = root.data // Assign product of minimum // and maximum value root.data = var1.min * var1.max // Again store min by considering // current node value var1.min = Math.min(var1.min, currData) // Again store max by considering // current node value var1.max = Math.max(var1.max, currData) return var1}function printt(root){ // Base Case if (root == null) return // Create an empty queue for // level order traversal q = [] // Enqueue Root and initialize // height q.push(root) while (q.length > 0) { // nodeCount (queue size) // indicates number // of nodes at current level. nodeCount = q.length // Dequeue all nodes of current // level and Enqueue all nodes // of next level while (nodeCount > 0) { node = q.shift() process.stdout.write(node.data + " ") if (node.left != null) q.push(node.left) if (node.right != null) q.push(node.right) nodeCount -= 1 } }}function minMaxProductTree(root) { // Utility Function call minMaxTreeUtil(root) // Print tree printt(root) }// Driver Code // /* 10 // / \ // 48 3 // / \ // 11 37 // / \ / \ // 7 29 42 19 // / // 7 // */ // Create Binary Tree as shown root = new Node(10) root.left = new Node(48) root.right = new Node(3) root.right.left = new Node(11) root.right.right = new Node(37) root.right.left.left = new Node(7) root.right.left.right = new Node(29) root.right.right.left = new Node(42) root.right.right.right =new Node(19) root.right.right.right.left = new Node(7) // Create Min Max Product Tree minMaxProductTree(root)// This code is contributed by phasing17 |
Output:
144 48 294 203 294 7 29 42 49 7
Time Complexity: O(N), where N denotes the number of nodes in the binary tree
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
