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 node struct Node { int data; struct Node *left, *right; }; // Utility function to create // a new node Node* 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 value struct minMax { int min; int max; }; // Function to return min value int 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 value int 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 value int min( int x, int y) { return x < y ? x : y; } // Function to return max value int max( int x, int y) { return x > y ? x : y; } // Utility function to create // min-max product tree minMax* 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 Code int 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 approach import java.util.*; // A Tree node class 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 value class 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 approach from collections import deque # A Tree node class Node: def __init__( self , x): self .data = x self .left = None self .right = None # A minMax Structure for storing # minimum and maximum value class minMax: def __init__( self , x, y): self . min = x self . max = y # Function to return min value def 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 value def 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 tree def 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 var def 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 - = 1 def minMaxProductTree(root): # Utility Function call minMaxTreeUtil(root) # Print tree printt(root) # Driver Code if __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 approach using System; using System.Collections.Generic; // A Tree node class 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 value class 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 node class Node { constructor(x) { this .data = x this .left = null this .right = null } } // A minMax Structure for storing // minimum and maximum value class minMax { constructor(x, y) { this .min = x this .max = y } } // Function to return min value function 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 value function 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 tree function 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 |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!