Approach :- Using Postorder Traversal of Tree
- The idea is to traverse the tree in postorder fashion .
- Recursively , call the left subtree.
- Recursively , call the right subtree.
- Get , the product of left child and right child and update the max variable and max parent variable with parent root of left and right child.
- Here , max parent variable will be storing the parent node of the maximum product siblings.
Below is the Implementation of this Approach :-
C++
#include <climits> #include <iostream> // Structure for Node struct Node { int data; Node* left; Node* right; Node( int data) : data(data) , left(nullptr) , right(nullptr) { } }; // Function to get a new node Node* getNode( int data) { // Allocate space Node* newNode = new Node(data); // Put in the data newNode->data = data; newNode->left = newNode->right = nullptr; return newNode; } // Initialize, parentNode with -1 int parentNode = -1; // Initialize, maxProductVal with INT_MIN int maxProductVal = INT_MIN; // Forward declaration of the helper function int helper(Node* root); // Function to get the parent of siblings with maximum // product int calculateMaxProduct(Node* root) { // calling helper function to get ParentNode helper(root); return parentNode; } int helper(Node* root) { // Base Case if (root == nullptr) { return 0; } // recursively, calling left part int left = helper(root->left); // recursively, calling right part int right = helper(root->right); // multiplying left and right to get product of the root int currProduct = left * right; // update maxProduct if (maxProductVal < currProduct) { maxProductVal = currProduct; // update the parentNode parentNode = root->data; } // return root data for every node return root->data; } // Driver Code int main() { /* * Binary tree creation * 1 * / \ * 3 5 * / \ / \ * 6 9 4 8 */ Node* root = getNode(1); root->left = getNode(3); root->right = getNode(5); root->left->left = getNode(6); root->left->right = getNode(9); root->right->left = getNode(4); root->right->right = getNode(8); std::cout << calculateMaxProduct(root) << std::endl; // Free allocated memory delete root->left->left; delete root->left->right; delete root->right->left; delete root->right->right; delete root->left; delete root->right; delete root; return 0; } |
Java
// Java code to find the Parent Node // of maximum product Siblings // in given Binary Tree import java.util.LinkedList; import java.util.Queue; class GFG { // Structure for Node static class Node { int data; Node left; Node right; public Node( int data) { this .data = data; this .left = null ; this .right = null ; } }; // Function to get a new node public static Node getNode( int data) { // Allocate space Node newNode = new Node(data); // Put in the data newNode.data = data; newNode.left = newNode.right = null ; return newNode; } // Initialize , parentNode with -1 static int parentNode = - 1 ; // Initialize , maxProduct with INT_MIN static int maxProduct = Integer.MIN_VALUE; // Function to get the parent // of siblings with maximum product public static int maxproduct(Node root) { // calling helper function to get // ParentNode helper(root); return parentNode; } static int helper(Node root) { // Base Case if (root == null ) { return 0 ; } // recursively , calling left part int left = helper(root.left); // recursively , calling right part int right = helper(root.right); // multiplying left and right to get product // of the root int currProduct = left * right; // update maxProduct if (maxProduct < currProduct) { maxProduct = currProduct; // update the parentNode parentNode = root.data; } // return root data for every node return root.data; } // Driver Code public static void main(String args[]) { /* * Binary tree creation * 1 * / \ * 3 5 * / \ / \ * 6 9 4 8 */ Node root = getNode( 1 ); root.left = getNode( 3 ); root.right = getNode( 5 ); root.left.left = getNode( 6 ); root.left.right = getNode( 9 ); root.right.left = getNode( 4 ); root.right.right = getNode( 8 ); System.out.println(maxproduct(root)); } } // This code is contributed by srimann7 |
Python
import sys # Class definition for Node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # Function to get a new node def get_node(data): # Allocate space new_node = Node(data) # Put in the data new_node.data = data new_node.left = new_node.right = None return new_node # Initialize parentNode with -1 parent_node = - 1 # Initialize max_product_val with INT_MIN max_product_val = - sys.maxsize - 1 # Helper function to calculate the maximum product def helper(root): global parent_node, max_product_val # Base Case if root is None : return 0 # Recursively calling left part left = helper(root.left) # Recursively calling right part right = helper(root.right) # Multiplying left and right to get the product of the root curr_product = left * right # Update max_product_val if max_product_val < curr_product: max_product_val = curr_product # Update the parent_node parent_node = root.data # Return root data for every node return root.data # Function to calculate the parent of siblings with the maximum product def calculate_max_product(root): # Calling the helper function to get parent_node helper(root) return parent_node # Driver Code if __name__ = = "__main__" : """ Binary tree creation 1 / \ 3 5 / \ / \ 6 9 4 8 """ root = get_node( 1 ) root.left = get_node( 3 ) root.right = get_node( 5 ) root.left.left = get_node( 6 ) root.left.right = get_node( 9 ) root.right.left = get_node( 4 ) root.right.right = get_node( 8 ) print (calculate_max_product(root)) # Free allocated memory del root.left.left del root.left.right del root.right.left del root.right.right del root.left del root.right del root |
C#
using System; // Structure for Node public class Node { public int data; public Node left; public Node right; public Node( int data) { this .data = data; this .left = null ; this .right = null ; } } public class BinaryTree { // Initialize parentNode with -1 private static int parentNode = -1; // Initialize maxProductVal with int.MinValue private static int maxProductVal = int .MinValue; // Function to get the parent of siblings with maximum // product private static int CalculateMaxProduct(Node root) { // calling helper function to get parentNode Helper(root); return parentNode; } private static int Helper(Node root) { // Base Case if (root == null ) { return 0; } // Recursively calling the left part int left = Helper(root.left); // Recursively calling the right part int right = Helper(root.right); // Multiplying left and right to get the product of // the root int currProduct = left * right; // Update maxProduct if (maxProductVal < currProduct) { maxProductVal = currProduct; // Update the parentNode parentNode = root.data; } // Return root data for every node return root.data; } // Driver Code public static void Main() { /* * Binary tree creation * 1 * / \ * 3 5 * / \ / \ * 6 9 4 8 */ Node root = new Node(1); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(6); root.left.right = new Node(9); root.right.left = new Node(4); root.right.right = new Node(8); Console.WriteLine(CalculateMaxProduct(root)); // No need to free memory in C#, as it is managed by // the garbage collector } } |
Javascript
// Structure for Node class Node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // Function to get a new node function getNode(data) { const newNode = new Node(data); newNode.data = data; newNode.left = null ; newNode.right = null ; return newNode; } // Initialize parentNode with -1 let parentNode = -1; // Initialize maxProductVal with Number.MIN_SAFE_INTEGER let maxProductVal = Number.MIN_SAFE_INTEGER; // Forward declaration of the helper function function helper(root) { // Base Case if (root === null ) { return 0; } // Recursively calling left part const left = helper(root.left); // Recursively calling right part const right = helper(root.right); // Multiplying left and right to get product of the root const currProduct = left * right; // Update maxProduct if (maxProductVal < currProduct) { maxProductVal = currProduct; // Update the parentNode parentNode = root.data; } // Return root data for every node return root.data; } // Function to get the parent of siblings with maximum product function calculateMaxProduct(root) { // Calling helper function to get parentNode helper(root); return parentNode; } // Driver Code /* * Binary tree creation * 1 * / \ * 3 5 * / \ / \ * 6 9 4 8 */ const root = getNode(1); root.left = getNode(3); root.right = getNode(5); root.left.left = getNode(6); root.left.right = getNode(9); root.right.left = getNode(4); root.right.right = getNode(8); console.log(calculateMaxProduct(root)); |
3
Time Complexity: O(N) , where N is the number of nodes in the tree
Auxiliary Space : O(N) , recursion stack space
Find the parent node of maximum product Siblings in given Binary Tree
Given a binary tree, the task is to find the node whose children have maximum Sibling product in the given Binary Tree. If there are multiple such nodes, return the node which has the maximum value.
Examples:
Input: Tree:
4
/ \
5 2
/ \
3 1
/ \
6 12
Output: 3
Explanation: For the above tree, the maximum product for the siblings is formed for nodes 6 and 12 which are the children of node 3.Input: Tree:
1
/ \
3 5
/ \ / \
6 9 4 8
Output: 3
Explanation: For the above tree, the maximum product for the siblings is formed for nodes 6 and 9 which are the children of node 3.