Given a Binary Tree, the task is to print the count of nodes having both children and both of them are its prime factors.
Examples:
Input:
1
/ \
15 20
/ \ / \
3 5 4 2
\ /
2 3
Output: 1
Explanation:
Children of 15 (3, 5) are prime factors of 15
Input:
7
/ \
210 14
/ \ \
70 14 30
/ \ / \
2 5 3 5
/
23
Output: 2
Explanation:
Children of 70 (2, 5) are prime factors of 70
Children of 30 (3, 5) are prime factors of 30
Approach:
- Traverse the given Binary Tree and for each node, check both the children exists or not.
- If both the children exist, check if each child is a prime factor of this node or not.
- Keep the count of such nodes and print it at the end.
- In order to check if a factor is prime, we will use Sieve to precompute the prime numbers to do the checking in O(1).
Below is the implementation of the above approach.
C++
// C++ program for Counting nodes// whose immediate children are its factors#include <bits/stdc++.h>using namespace std;int N = 1000000;// To store all prime numbersvector<int> prime;void SieveOfEratosthenes(){ // Create a boolean array "prime[0..N]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. bool check[N + 1]; memset(check, true, sizeof(check)); for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (check[p] == true) { prime.push_back(p); // Update all multiples of p // greater than or equal to // the square of it // numbers which are multiples of p // and are less than p^2 // are already marked. for (int i = p * p; i <= N; i += p) check[i] = false; } }}// A Tree nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// function to check and print if// immediate children of a node// are its factors or notbool areChilrenPrimeFactors(struct Node* parent, struct Node* a, struct Node* b){ if (prime[a->key] && prime[b->key] && (parent->key % a->key == 0 && parent->key % b->key == 0)) return true; else return false;}// Function to get the count of full Nodes in// a binary treeunsigned int getCount(struct Node* node){ // If tree is empty if (!node) return 0; queue<Node*> q; // Initialize count of full nodes // having children as their factors int count = 0; // Do level order traversal // starting from root q.push(node); while (!q.empty()) { struct Node* temp = q.front(); q.pop(); if (temp->left && temp->right) { if (areChilrenPrimeFactors( temp, temp->left, temp->right)) count++; } if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); } return count;}// Function to find total no of nodes// In a given binary treeint findSize(struct Node* node){ // Base condition if (node == NULL) return 0; return 1 + findSize(node->left) + findSize(node->right);}// Driver Codeint main(){ /* 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 2 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(2); root->right = newNode(5); root->right->left = newNode(18); root->right->right = newNode(12); root->right->left->left = newNode(2); root->right->left->right = newNode(3); root->right->right->left = newNode(3); root->right->right->right = newNode(2); root->right->right->right->left = newNode(7); // To save all prime numbers SieveOfEratosthenes(); // Print all nodes having // children as their factors cout << getCount(root) << endl; return 0;} |
Java
// Java program for Counting nodes// whose immediate children are its factorsimport java.util.*;class GFG{ static int N = 1000000; // To store all prime numbersstatic Vector<Integer> prime = new Vector<Integer>(); static void SieveOfEratosthenes(){ // Create a boolean array "prime[0..N]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. boolean []check = new boolean[N + 1]; Arrays.fill(check, true); for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (check[p] == true) { prime.add(p); // Update all multiples of p // greater than or equal to // the square of it // numbers which are multiples of p // and are less than p^2 // are already marked. for (int i = p * p; i <= N; i += p) check[i] = false; } }} // A Tree nodestatic class Node { int key; Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // function to check and print if// immediate children of a node// are its factors or notstatic boolean areChilrenPrimeFactors(Node parent, Node a, Node b){ if (prime.get(a.key) != null && prime.get(b.key) != null && (parent.key % a.key == 0 && parent.key % b.key == 0)) return true; else return false;} // Function to get the count of full Nodes in// a binary treestatic int getCount(Node node){ // If tree is empty if (node == null) return 0; Queue<Node> q = new LinkedList<>(); // Initialize count of full nodes // having children as their factors int count = 0; // Do level order traversal // starting from root q.add(node); while (!q.isEmpty()) { Node temp = q.peek(); q.remove(); if (temp.left!=null && temp.right != null) { if (areChilrenPrimeFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } return count;} // Function to find total no of nodes// In a given binary treestatic int findSize(Node node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Driver Codepublic static void main(String[] args){ /* 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 2 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(2); root.right = newNode(5); root.right.left = newNode(18); root.right.right = newNode(12); root.right.left.left = newNode(2); root.right.left.right = newNode(3); root.right.right.left = newNode(3); root.right.right.right = newNode(2); root.right.right.right.left = newNode(7); // To save all prime numbers SieveOfEratosthenes(); // Print all nodes having // children as their factors System.out.print(getCount(root) +"\n"); }}// This code is contributed by Rajput-Ji |
Python3
#Python3 code for the above approachfrom typing import ListN = 1000000# To store all prime numbersprime = []def sieve_of_eratosthenes(): # Create a boolean array "prime[0..N]" # and initialize all entries it as true. # A value in prime[i] will finally # be false if i is Not a prime, else true. check = [True] * (N + 1) for p in range(2, int(N ** 0.5) + 1): # If prime[p] is not changed, # then it is a prime if check[p]: prime.append(p) # Update all multiples of p # greater than or equal to # the square of it # numbers which are multiples of p # and are less than p^2 # are already marked. for i in range(p * p, N + 1, p): check[i] = False# A Tree nodeclass Node: def __init__(self, key: int): self.key = key self.left = None self.right = None# Utility function to create a new nodedef new_node(key: int) -> Node: temp = Node(key) return temp# function to check and print if# immediate children of a node# are its factors or notdef are_children_prime_factors(parent: Node, a: Node, b: Node) -> bool: if prime[a.key] and prime[b.key] and (parent.key % a.key == 0 and parent.key % b.key == 0): return True else: return False# Function to get the count of full Nodes in# a binary treedef get_count(node: Node) -> int: # If tree is empty if not node: return 0 q = [] # Initialize count of full nodes # having children as their factors count = 0 # Do level order traversal # starting from root q.append(node) while q: temp = q.pop(0) if temp.left and temp.right: if are_children_prime_factors(temp, temp.left, temp.right): count += 1 if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) return count# Function to find total no of nodes# In a given binary treedef find_size(node: Node) -> int: # Base condition if not node: return 0 return 1 + find_size(node.left) + find_size(node.right)if __name__ == "__main__": """ 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 2 / 7 """ # Create Binary Tree as shown root = new_node(10) root.left = new_node(2) root.right = new_node(5) root.right.left = new_node(18) root.right.right = new_node(12) root.right.left.left = new_node(2) root.right.left.right = new_node(3) root.right.right.left = new_node(3) root.right.right.right = new_node(2) root.right.right.right.left = new_node(7) # To save all prime numbers sieve_of_eratosthenes() print( get_count(root))#This code is contributed by Potta Lokesh |
C#
// C# program for Counting nodes// whose immediate children are its factorsusing System;using System.Collections.Generic;class GFG{ static int N = 1000000; // To store all prime numbersstatic List<int> prime = new List<int>(); static void SieveOfEratosthenes(){ // Create a bool array "prime[0..N]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. bool []check = new bool[N + 1]; for (int i = 0; i <= N; i += 1){ check[i] = true; } for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (check[p] == true) { prime.Add(p); // Update all multiples of p // greater than or equal to // the square of it // numbers which are multiples of p // and are less than p^2 // are already marked. for (int i = p * p; i <= N; i += p) check[i] = false; } }} // A Tree nodeclass Node { public int key; public Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // function to check and print if// immediate children of a node// are its factors or notstatic bool areChilrenPrimeFactors(Node parent, Node a, Node b){ if (prime.Contains(a.key)&& prime.Contains(b.key) && (parent.key % a.key == 0 && parent.key % b.key == 0)) return true; else return false;} // Function to get the count of full Nodes in// a binary treestatic int getCount(Node node){ // If tree is empty if (node == null) return 0; List<Node> q = new List<Node>(); // Initialize count of full nodes // having children as their factors int count = 0; // Do level order traversal // starting from root q.Add(node); while (q.Count!=0) { Node temp = q[0]; q.RemoveAt(0); if (temp.left!=null && temp.right != null) { if (areChilrenPrimeFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.Add(temp.left); if (temp.right != null) q.Add(temp.right); } return count;} // Function to find total no of nodes// In a given binary treestatic int findSize(Node node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Driver Codepublic static void Main(String[] args){ /* 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 2 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(2); root.right = newNode(5); root.right.left = newNode(18); root.right.right = newNode(12); root.right.left.left = newNode(2); root.right.left.right = newNode(3); root.right.right.left = newNode(3); root.right.right.right = newNode(2); root.right.right.right.left = newNode(7); // To save all prime numbers SieveOfEratosthenes(); // Print all nodes having // children as their factors Console.Write(getCount(root) +"\n"); }} // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program for Counting nodes // whose immediate children are its factors let N = 1000000; // To store all prime numbers let prime = []; function SieveOfEratosthenes() { // Create a boolean array "prime[0..N]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. let check = new Array(N + 1); check.fill(true); for (let p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (check[p] == true) { prime.push(p); // Update all multiples of p // greater than or equal to // the square of it // numbers which are multiples of p // and are less than p^2 // are already marked. for (let i = p * p; i <= N; i += p) check[i] = false; } } } // A Tree node class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } } // Utility function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // function to check and print if // immediate children of a node // are its factors or not function areChilrenPrimeFactors(parent, a, b) { if (prime[a.key] != null && prime[b.key] != null && (parent.key % a.key == 0 && parent.key % b.key == 0)) return true; else return false; } // Function to get the count of full Nodes in // a binary tree function getCount(node) { // If tree is empty if (node == null) return 0; let q = []; // Initialize count of full nodes // having children as their factors let count = 0; // Do level order traversal // starting from root q.push(node); while (q.length > 0) { let temp = q[0]; q.shift(); if (temp.left!=null && temp.right != null) { if (areChilrenPrimeFactors( temp, temp.left, temp.right)) count++; } if (temp.left != null) q.push(temp.left); if (temp.right != null) q.push(temp.right); } return count; } // Function to find total no of nodes // In a given binary tree function findSize(node) { // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right); } /* 10 / \ 2 5 / \ 18 12 / \ / \ 2 3 3 2 / 7 */ // Create Binary Tree as shown let root = newNode(10); root.left = newNode(2); root.right = newNode(5); root.right.left = newNode(18); root.right.right = newNode(12); root.right.left.left = newNode(2); root.right.left.right = newNode(3); root.right.right.left = newNode(3); root.right.right.right = newNode(2); root.right.right.right.left = newNode(7); // To save all prime numbers SieveOfEratosthenes(); // Print all nodes having // children as their factors document.write(getCount(root) +"</br>");</script> |
Output:
3
Time complexity: O(N * log(log(N))). //N is the maximum value of a key in the binary tree.
Space complexity: 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 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
