Count of nodes in a Binary Tree whose immediate children are co-prime
Given a Binary Tree, the task is to count the nodes whose immediate children are co-prime.
Examples:
Input: 1 / \ 15 5 / \ / \ 11 2 4 15 \ / 2 3 Output: 2 Explanation: Children of 15 (11, 2) are co-prime Children of 5 (4, 15) are co-prime Input: 7 / \ 21 14 / \ \ 77 16 3 / \ / \ 2 5 10 11 / 23 Output:3 Explanation: Children of 21 (77, 8) are co-prime Children of 77 (2, 5) are co-prime Children of 3 (10, 11) are co-prime
Approach: The idea is to:
- Do level order traversal of the tree
- For each node check that its both children are not Null
- If true, then check whether greatest common divisor of both children is 1.
- If yes, then count such nodes and print at the end.
Below is the implementation of the above approach:
C++
// C++ program for Counting nodes // whose immediate children // are co-prime #include <bits/stdc++.h> using namespace std; // Structure of node struct Node { int key; struct Node *left, *right; }; // Utility function to // create a new node Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp); } // Function to check and print if // two nodes are co-prime or not bool coprime( struct Node* a, struct Node* b) { if (__gcd(a->key, b->key) == 1) return true ; else return false ; } // Function to get the count of // Nodes whose immediate children // are co-prime in a binary tree unsigned int getCount( struct Node* node) { // Base Case if (!node) return 0; queue<Node*> q; // Do level order traversal // starting from root int count = 0; q.push(node); while (!q.empty()) { struct Node* temp = q.front(); q.pop(); if (temp->left && temp->right) { if (coprime(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 // number of nodes // In a given binary tree int findSize( struct Node* node) { // Base condition if (node == NULL) return 0; return 1 + findSize(node->left) + findSize(node->right); } // Function to create Tree // and find the count of nodes // whose immediate children // are co-prime void findCount() { /* 10 / \ 48 12 / \ 18 35 / \ / \ 21 29 43 16 / 7 */ // Create Binary Tree Node* root = newNode(10); root->left = newNode(48); root->right = newNode(12); root->right->left = newNode(18); root->right->right = newNode(35); root->right->left->left = newNode(21); root->right->left->right = newNode(29); root->right->right->left = newNode(43); root->right->right->right = newNode(16); root->right->right->right->left = newNode(7); // Print all nodes // with Co-Prime children cout << getCount(root) << endl; } // Driver Code int main() { // Function Call findCount(); return 0; } |
Java
// Java program for Counting nodes // whose immediate children // are co-prime import java.util.*; class GFG{ // Structure of node static class Node { int key; Node left, right; }; // Utility function to // create a new node static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null ; return (temp); } // Function to check and print if // two nodes are co-prime or not static boolean coprime(Node a, Node b) { if (__gcd(a.key, b.key) == 1 ) return true ; else return false ; } // Function to get the count of // Nodes whose immediate children // are co-prime in a binary tree static int getCount(Node node) { // Base Case if (node == null ) return 0 ; Queue<Node> q = new LinkedList<Node>(); // Do level order traversal // starting from root int count = 0 ; q.add(node); while (!q.isEmpty()) { Node temp = q.peek(); q.remove(); if (temp.left != null && temp.right != null ) { if (coprime(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 // number of nodes // In a given binary tree static int findSize(Node node) { // Base condition if (node == null ) return 0 ; return 1 + findSize(node.left) + findSize(node.right); } // Function to create Tree // and find the count of nodes // whose immediate children // are co-prime static void findCount() { /* 10 / \ 48 12 / \ 18 35 / \ / \ 21 29 43 16 / 7 */ // Create Binary Tree Node root = newNode( 10 ); root.left = newNode( 48 ); root.right = newNode( 12 ); root.right.left = newNode( 18 ); root.right.right = newNode( 35 ); root.right.left.left = newNode( 21 ); root.right.left.right = newNode( 29 ); root.right.right.left = newNode( 43 ); root.right.right.right = newNode( 16 ); root.right.right.right.left = newNode( 7 ); // Print all nodes // with Co-Prime children System.out.print(getCount(root) + "\n" ); } static int __gcd( int a, int b) { return b == 0 ? a:__gcd(b, a % b); } // Driver Code public static void main(String[] args) { // Function Call findCount(); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 program for counting nodes # whose immediate children # are co-prime from collections import deque as queue from math import gcd as __gcd # A Binary Tree Node class Node: def __init__( self , key): self .data = key self .left = None self .right = None # Function to check and print if # two nodes are co-prime or not def coprime(a, b): if (__gcd(a.data, b.data) = = 1 ): return True else : return False # Function to get the count of # Nodes whose immediate children # are co-prime in a binary tree def getCount(node): # Base Case if ( not node): return 0 q = queue() # Do level order traversal # starting from root count = 0 q.append(node) while ( len (q) > 0 ): temp = q.popleft() #q.pop() if (temp.left and temp.right): if (coprime(temp.left, temp.right)): count + = 1 if (temp.left ! = None ): q.append(temp.left) if (temp.right ! = None ): q.append(temp.right) return count # Function to find total # number of nodes # In a given binary tree def findSize(node): # Base condition if (node = = None ): return 0 return ( 1 + findSize(node.left) + findSize(node.right)) # Function to create Tree # and find the count of nodes # whose immediate children # are co-prime def findCount(): # 10 # / \ # 48 12 # / \ # 18 35 # / \ / \ # 21 29 43 16 # / # 7 # # Create Binary Tree root = Node( 10 ) root.left = Node( 48 ) root.right = Node( 12 ) root.right.left = Node( 18 ) root.right.right = Node( 35 ) root.right.left.left = Node( 21 ) root.right.left.right = Node( 29 ) root.right.right.left = Node( 43 ) root.right.right.right = Node( 16 ) root.right.right.right.left = Node( 7 ) # Print all nodes # with Co-Prime children print (getCount(root)) # Driver Code if __name__ = = '__main__' : # Function Call findCount() # This code is contributed by mohit kumar 29 |
C#
// C# program for Counting nodes // whose immediate children // are co-prime using System; using System.Collections.Generic; class GFG{ // Structure of node class Node { public int key; public Node left, right; }; // Utility function to // create a new node static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null ; return (temp); } // Function to check and print if // two nodes are co-prime or not static bool coprime(Node a, Node b) { if (__gcd(a.key, b.key) == 1) return true ; else return false ; } // Function to get the count of // Nodes whose immediate children // are co-prime in a binary tree static int getCount(Node node) { // Base Case if (node == null ) return 0; List<Node> q = new List<Node>(); // Do level order traversal // starting from root int count = 0; q.Add(node); while (q.Count != 0) { Node temp = q[0]; q.RemoveAt(0); if (temp.left != null && temp.right != null ) { if (coprime(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 // number of nodes // In a given binary tree static int findSize(Node node) { // Base condition if (node == null ) return 0; return 1 + findSize(node.left) + findSize(node.right); } // Function to create Tree // and find the count of nodes // whose immediate children // are co-prime static void findCount() { /* 10 / \ 48 12 / \ 18 35 / \ / \ 21 29 43 16 / 7 */ // Create Binary Tree Node root = newNode(10); root.left = newNode(48); root.right = newNode(12); root.right.left = newNode(18); root.right.right = newNode(35); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(16); root.right.right.right.left = newNode(7); // Print all nodes // with Co-Prime children Console.Write(getCount(root) + "\n" ); } static int __gcd( int a, int b) { return b == 0? a:__gcd(b, a % b); } // Driver Code public static void Main(String[] args) { // Function Call findCount(); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for counting nodes // whose immediate children are co-prime // Structure of node class Node { // Utility function to // create a new node constructor(key) { this .key = key; this .left = this .right = null ; } } // Function to check and print if // two nodes are co-prime or not function coprime(a, b) { if (__gcd(a.key, b.key) == 1) return true ; else return false ; } // Function to get the count of // Nodes whose immediate children // are co-prime in a binary tree function getCount(node) { // Base Case if (node == null ) return 0; let q = []; // Do level order traversal // starting from root let count = 0; q.push(node); while (q.length != 0) { let temp = q.shift(); if (temp.left != null && temp.right != null ) { if (coprime(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 // number 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); } // Function to create Tree // and find the count of nodes // whose immediate children // are co-prime function findCount() { /* 10 / \ 48 12 / \ 18 35 / \ / \ 21 29 43 16 / 7 */ // Create Binary Tree let root = new Node(10); root.left = new Node(48); root.right = new Node(12); root.right.left = new Node(18); root.right.right = new Node(35); root.right.left.left = new Node(21); root.right.left.right = new Node(29); root.right.right.left = new Node(43); root.right.right.right = new Node(16); root.right.right.right.left = new Node(7); // Print all nodes // with Co-Prime children document.write(getCount(root) + "<br>" ); } function __gcd(a,b) { return b == 0? a:__gcd(b, a % b); } // Driver Code // Function Call findCount(); // This code is contributed by patel2127 </script> |
3
Complexity Analysis:
Time Complexity: O(N*logV) where V is the weight of a node in the tree.
In bfs, every node of the tree is processed once and hence the complexity due to the bfs is O(N) if there are total N nodes in the tree. Also, while processing every node, in order to check if the node values are co-prime or not, the inbuilt __gcd(A, B) function where A, B are the weight of the nodes is being called and this function has a complexity of O(log(min(A, B))), hence for every node there is an added complexity of O(logV). Therefore, the time complexity is O(N*logV).
Auxiliary Space : O(w) where w is the maximum width of the tree.