Given a binary tree, the task is to find the product of the smallest and largest prime numbers in a given binary tree.
Examples:
Input:
4
/ \
5 7
/ \ / \
1 3 5 8Output: 21
Input:
6
/ \
8 11
/ \ / \
4 3 9 15Output: 33
Approach: This can be solved with the following idea:
The main idea behind this approach is to perform an in-order traversal of the binary tree and store all the prime numbers in a vector. Once we have all the prime numbers in the vector, we can easily find the minimum and maximum prime numbers in the vector and return their product. We perform an in-order traversal of the binary tree to visit each node of the tree. At each node, we check if the node’s value is prime or not. If the value is prime, we add it to a vector.
Steps involved in the implementation of code:
- In the isPrime() function Check if the value of n is less than or equal to 1. If true, return false as 1.
- Loop from 2 to sqrt(n) and check if the number is divisible by any of these numbers.
- If n is divisible by i (i.e., n%i == 0), return false as n is not prime.
- If the loop finishes without finding a factor, return true as n is prime.
- In the inorder() function Check if the root is null. If true, return from the function.
- Recursively call in order with the left child of the root and the same vector as inputs.
- Check if the value of the root is prime. If true, add the value to the vector.
- Recursively call in order with the right child of the root and the same vector as inputs.
- Once we have all the prime numbers in the vector, we can find the minimum and maximum prime numbers in the vector using a loop.
- We initialize the minimum and maximum prime numbers to the maximum and minimum integer values, respectively, and then iterate through the vector of prime numbers.
- At each iteration, we check if the current prime number is smaller than the current minimum prime number, and update the minimum prime number if it is.
- Similarly, we check if the current prime number is larger than the current maximum prime number, and update the maximum prime number if it is.
- Finally, we return the product of the smallest and largest prime numbers found in the vector.
Below is the implementation of the above approach:
C++
// C++ code of the above approach#include <bits/stdc++.h>using namespace std;// Structure of treestruct Node { int val; Node *left, *right;};// Function to create a new nodeNode* createNode(int val){ Node* newNode = new Node; newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode;}// Function to check if a number// is prime or notbool isPrime(int n){ if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true;}// Function to perform inorder traversal// of the binary tree and store all the// prime numbers in a vectorvoid inorder(Node* root, vector<int>& primes){ if (root == NULL) return; inorder(root->left, primes); if (isPrime(root->val)) primes.push_back(root->val); inorder(root->right, primes);}// Function to get maximum productvoid maxProduct(Node* root){ vector<int> primes; // Traverse inorder(root, primes); int n = primes.size(); // If no prime number is there if (n == 0) cout << endl; else { int minPrime = INT_MAX; int maxPrime = INT_MIN; for (int i = 0; i < n; i++) { if (primes[i] < minPrime) minPrime = primes[i]; if (primes[i] > maxPrime) maxPrime = primes[i]; } // Get the product cout << minPrime * maxPrime << endl; }}// Driver codeint main(){ Node* root = createNode(4); root->left = createNode(5); root->right = createNode(7); root->left->left = createNode(1); root->left->right = createNode(3); root->right->left = createNode(5); root->right->right = createNode(8); // Function call maxProduct(root); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.ArrayList;import java.util.List;// Structure of treeclass Node { int val; Node left, right;}public class Main { // Function to create a new node static Node createNode(int val) { Node newNode = new Node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode; } // Function to check if a number is prime or not static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // Function to perform inorder traversal of the binary tree and store all the prime numbers in a list static void inorder(Node root, List<Integer> primes) { if (root == null) return; inorder(root.left, primes); if (isPrime(root.val)) primes.add(root.val); inorder(root.right, primes); } // Function to get maximum product static void maxProduct(Node root) { List<Integer> primes = new ArrayList<>(); // Traverse inorder(root, primes); int n = primes.size(); // If no prime number is there if (n == 0) System.out.println(); else { int minPrime = Integer.MAX_VALUE; int maxPrime = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { if (primes.get(i) < minPrime) minPrime = primes.get(i); if (primes.get(i) > maxPrime) maxPrime = primes.get(i); } // Get the product System.out.println(minPrime * maxPrime); } } // Driver code public static void main(String[] args) { Node root = createNode(4); root.left = createNode(5); root.right = createNode(7); root.left.left = createNode(1); root.left.right = createNode(3); root.right.left = createNode(5); root.right.right = createNode(8); // Function call maxProduct(root); }}//This code is contributed by Sameer Hake |
Python3
# Structure of treeclass Node: def __init__(self, val): self.val = val self.left = None self.right = None# Function to create a new nodedef createNode(val): newNode = Node(val) return newNode# Function to check if a number is prime or notdef isPrime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True# Function to perform inorder traversal# of the binary tree and store all the# prime numbers in a listdef inorder(root, primes): if root is None: return inorder(root.left, primes) if isPrime(root.val): primes.append(root.val) inorder(root.right, primes)# Function to get maximum productdef maxProduct(root): primes = [] # Traverse inorder(root, primes) n = len(primes) # If no prime number is there if n == 0: print() else: minPrime = float('inf') maxPrime = float('-inf') for i in range(n): if primes[i] < minPrime: minPrime = primes[i] if primes[i] > maxPrime: maxPrime = primes[i] # Get the product print(minPrime * maxPrime)# Driver codeif __name__ == '__main__': root = createNode(4) root.left = createNode(5) root.right = createNode(7) root.left.left = createNode(1) root.left.right = createNode(3) root.right.left = createNode(5) root.right.right = createNode(8) # Function call maxProduct(root) |
C#
using System;using System.Collections.Generic;// Structure of treeclass Node { public int val; public Node left, right;}class Program { // Function to create a new node static Node CreateNode(int val) { Node newNode = new Node(); newNode.val = val; newNode.left = null; newNode.right = null; return newNode; } // Function to check if a number is prime or not static bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // Function to perform inorder traversal of the binary tree and store all the prime numbers in a list static void Inorder(Node root, List<int> primes) { if (root == null) return; Inorder(root.left, primes); if (IsPrime(root.val)) primes.Add(root.val); Inorder(root.right, primes); } // Function to get maximum product static void MaxProduct(Node root) { List<int> primes = new List<int>(); // Traverse Inorder(root, primes); int n = primes.Count; // If no prime number is there if (n == 0) Console.WriteLine(); else { int minPrime = int.MaxValue; int maxPrime = int.MinValue; for (int i = 0; i < n; i++) { if (primes[i] < minPrime) minPrime = primes[i]; if (primes[i] > maxPrime) maxPrime = primes[i]; } // Get the product Console.WriteLine(minPrime * maxPrime); } } // Driver code static void Main(string[] args) { Node root = CreateNode(4); root.left = CreateNode(5); root.right = CreateNode(7); root.left.left = CreateNode(1); root.left.right = CreateNode(3); root.right.left = CreateNode(5); root.right.right = CreateNode(8); // Function call MaxProduct(root); }}//This code is contributed by Sameer Hake |
Javascript
// Structure of treeclass Node { constructor(val) { this.val = val; this.left = null; this.right = null; }}// Function to check if a number is prime or notfunction isPrime(n) { if (n <= 1) return false; for (let i = 2; i * i <= n; i++) { if (n % i === 0) return false; } return true;}// Function to perform inorder traversal of the binary tree and store all the prime numbers in an arrayfunction inorder(root, primes) { if (root === null) return; inorder(root.left, primes); if (isPrime(root.val)) primes.push(root.val); inorder(root.right, primes);}// Function to get maximum productfunction maxProduct(root) { let primes = []; // Traverse inorder(root, primes); let n = primes.length; // If no prime number is there if (n === 0) console.log(); else { let minPrime = Number.MAX_SAFE_INTEGER; let maxPrime = Number.MIN_SAFE_INTEGER; for (let i = 0; i < n; i++) { if (primes[i] < minPrime) minPrime = primes[i]; if (primes[i] > maxPrime) maxPrime = primes[i]; } // Get the product console.log(minPrime * maxPrime); }}// Driver codelet root = new Node(4);root.left = new Node(5);root.right = new Node(7);root.left.left = new Node(1);root.left.right = new Node(3);root.right.left = new Node(5);root.right.right = new Node(8);// Function callmaxProduct(root);//This code is contributed by Sameer Hake |
Output
21
Time Complexity: O(N sqrt(N))
Auxiliary Space: O(H)
Approach : Recursive Approach With Helper Functions
Using two helper functions: one to find the smallest prime number in the tree and another to find the largest prime
number. Both helper functions traverse the tree recursively and return the appropriate value. Last, we return
the product of the smallest and largest prime numbers found.
Below is the code implementation:
C++
#include <iostream>#include <climits>#include <cmath>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};// Function to check if a number is primebool isPrime(int n) { // 1 is not a prime number if (n <= 1) { return false; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true;}// Helper functionvoid findSmallestLargestPrimes(TreeNode* root, int& smallest, int& largest) { if (root == NULL) { return; } if (isPrime(root->val)) { if (root->val < smallest) { smallest = root->val; } if (root->val > largest) { largest = root->val; } } findSmallestLargestPrimes(root->left, smallest, largest); findSmallestLargestPrimes(root->right, smallest, largest);}// Main function to find the product of the smallest and largest prime numbers in a binary treeint findProductOfSmallestLargestPrimes(TreeNode* root) { int smallest = INT_MAX; int largest = INT_MIN; findSmallestLargestPrimes(root, smallest, largest); if (smallest == INT_MAX || largest == INT_MIN) { return -1; } return smallest * largest;}// Driver codeint main() { // Example 1: TreeNode* root1 = new TreeNode(4); root1->left = new TreeNode(5); root1->right = new TreeNode(7); root1->left->left = new TreeNode(1); root1->left->right = new TreeNode(3); root1->right->left = new TreeNode(5); root1->right->right = new TreeNode(8); cout << findProductOfSmallestLargestPrimes(root1) << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; left = null; right = null; }}public class Main { // Function to check if a number is prime static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // Helper function static void findSmallestLargestPrimes(TreeNode root, int[] smallest, int[] largest) { if (root == null) { return; } if (isPrime(root.val)) { if (root.val < smallest[0]) { smallest[0] = root.val; } if (root.val > largest[0]) { largest[0] = root.val; } } findSmallestLargestPrimes(root.left, smallest, largest); findSmallestLargestPrimes(root.right, smallest, largest); } // Main function to find the product of the smallest and largest prime numbers in a binary tree static int findProductOfSmallestLargestPrimes(TreeNode root) { int[] smallest = { Integer.MAX_VALUE }; int[] largest = { Integer.MIN_VALUE }; findSmallestLargestPrimes(root, smallest, largest); if (smallest[0] == Integer.MAX_VALUE || largest[0] == Integer.MIN_VALUE) { return -1; } return smallest[0] * largest[0]; } // Driver code public static void main(String[] args) { // Example 1: TreeNode root1 = new TreeNode(4); root1.left = new TreeNode(5); root1.right = new TreeNode(7); root1.left.left = new TreeNode(1); root1.left.right = new TreeNode(3); root1.right.left = new TreeNode(5); root1.right.right = new TreeNode(8); System.out.println(findProductOfSmallestLargestPrimes(root1)); }}//This code is contributed by Sameer Hake |
Python3
import mathclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None# Function to check if a number is primedef isPrime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True# Helper functiondef findSmallestLargestPrimes(root, smallest, largest): if root is None: return if isPrime(root.val): if root.val < smallest[0]: smallest[0] = root.val if root.val > largest[0]: largest[0] = root.val findSmallestLargestPrimes(root.left, smallest, largest) findSmallestLargestPrimes(root.right, smallest, largest)# Main function to find the product of the smallest and largest prime numbers in a binary treedef findProductOfSmallestLargestPrimes(root): smallest = [float('inf')] largest = [float('-inf')] findSmallestLargestPrimes(root, smallest, largest) if smallest[0] == float('inf') or largest[0] == float('-inf'): return -1 return smallest[0] * largest[0]# Driver code# Example 1:root1 = TreeNode(4)root1.left = TreeNode(5)root1.right = TreeNode(7)root1.left.left = TreeNode(1)root1.left.right = TreeNode(3)root1.right.left = TreeNode(5)root1.right.right = TreeNode(8)print(findProductOfSmallestLargestPrimes(root1)) |
C#
using System;class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class Program { // Function to check if a number is prime static bool IsPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // Helper function static void FindSmallestLargestPrimes(TreeNode root, ref int smallest, ref int largest) { if (root == null) { return; } if (IsPrime(root.val)) { if (root.val < smallest) { smallest = root.val; } if (root.val > largest) { largest = root.val; } } FindSmallestLargestPrimes(root.left, ref smallest, ref largest); FindSmallestLargestPrimes(root.right, ref smallest, ref largest); } // Main function to find the product of the smallest and largest prime numbers in a binary tree static int FindProductOfSmallestLargestPrimes(TreeNode root) { int smallest = int.MaxValue; int largest = int.MinValue; FindSmallestLargestPrimes(root, ref smallest, ref largest); if (smallest == int.MaxValue || largest == int.MinValue) { return -1; } return smallest * largest; } // Driver code public static void Main(string[] args) { // Example 1: TreeNode root1 = new TreeNode(4); root1.left = new TreeNode(5); root1.right = new TreeNode(7); root1.left.left = new TreeNode(1); root1.left.right = new TreeNode(3); root1.right.left = new TreeNode(5); root1.right.right = new TreeNode(8); Console.WriteLine(FindProductOfSmallestLargestPrimes(root1)); }}//This code is contributed by Sameer Hake |
Javascript
class TreeNode { constructor(x) { this.val = x; this.left = null; this.right = null; }}// Function to check if a number is primefunction isPrime(n) { if (n <= 1) { return false; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false; } } return true;}// Helper functionfunction findSmallestLargestPrimes(root, smallest, largest) { if (root === null) { return; } if (isPrime(root.val)) { if (root.val < smallest[0]) { smallest[0] = root.val; } if (root.val > largest[0]) { largest[0] = root.val; } } findSmallestLargestPrimes(root.left, smallest, largest); findSmallestLargestPrimes(root.right, smallest, largest);}// Main function to find the product of the smallest and largest prime numbers in a binary treefunction findProductOfSmallestLargestPrimes(root) { let smallest = [Number.MAX_VALUE]; let largest = [Number.MIN_VALUE]; findSmallestLargestPrimes(root, smallest, largest); if (smallest[0] === Number.MAX_VALUE || largest[0] === Number.MIN_VALUE) { return -1; } return smallest[0] * largest[0];}// Driver codelet root1 = new TreeNode(4);root1.left = new TreeNode(5);root1.right = new TreeNode(7);root1.left.left = new TreeNode(1);root1.left.right = new TreeNode(3);root1.right.left = new TreeNode(5);root1.right.right = new TreeNode(8);console.log(findProductOfSmallestLargestPrimes(root1)); |
Output
21
Time Complexity : O(N sqrt(N)), where N is the number of nodes in the binary tree.
Auxiliary Space : O(H), where H is the height of the binary 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!
Share your thoughts in the comments
