How to print Co-Prime levels in a Binary Tree in C++

By Sumanth

In this tutorial, we will learn how to print the co-prime levels of a binary tree in C++.

Printing Co-Prime levels in Binary Tree in C++

What is a Binary Tree?
A Binary Tree is basically a tree which consists of a parent node and each node has at most 2 children,
In C++ we can implement a Binary Tree using struct as follows

struct Node { 
    int data ; 
    struct Node *left,*right; //*left is the left child and *right is the right child
};

For more in-depth coverage on Binary trees in C++

Levels of a Binary Tree
Every tree consists of levels, in other words, each horizontal row of a tree can be called a level.

                         10         //level 0
              	       /    \
	              6      11     //level 1
                     / \    /  \
		    5   8  11  18   //level 2

What are Co-Prime levels?
Co-Prime : 2 numbers are said to be co-prime if their GCD is 1.

Levels of a Binary Tree that contains elements which are co-prime to each other are called co-prime levels.
In the above example level 1 is a co-prime level since its elements 6 and 11 are co-prime to each other.

Algorithm for finding Co-Prime levels of a Binary Tree
We can easily find out if a level of a tree is co-prime or not by taking all the elements of each level separately into a container like a vector or an array and then finding out the GCD of each level, If the GCD is 1 then that level is said to be Co-Prime.
For finding the gcd, we can make use of the C++ in-built __gcd function.

Code for finding and printing the co-prime levels of  Binary Tree in C++

#include <bits/stdc++.h> 
using namespace std; 
  


int findGCD(vector<int> vec, int n){ 
    int result = vec[0]; 

    for (int i = 1; i < n; i++) { 
        result = __gcd(vec[i], result); //Using in-built __gcd() method.
  
        if(result == 1){ 
           return 1; 
        } 
    } 
    return result; 
} 


// A Tree 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); 
} 
int totalChildrenInTheTree(struct Node* root){  
//Return the size of tree
    if (root == NULL) 
        return 0; 
  
    return (totalChildrenInTheTree(root->left)
           +totalChildrenInTheTree(root->right))
           +1;   //+1 is for the root
} 
    
void printCoPrimeLevels(vector<int>& level) 
{ 
    for (int num : level) { 
        cout << num << " "; 
    } 
    cout << endl; 
} 
  

void getCoPrimeLevels(struct Node* node) { 
    int s=totalChildrenInTheTree(node); 
    struct Node* queue[s];    //Queue of type Node*,
                               //to store the nodes of the tree.
    queue[0]=node;  
    vector<int> level;     //Container which we will use to
                           // store elements of each level.
    int index=0;
    int size=1;       
    
    //Loop from the first index=0 to the end of the tree.
    while (index < size) { 
        int csize = size; 
    
        //This loop is to process each level 
        // and to check if its co-prime or not
        while (index < csize) { 
            struct Node* temp = queue[index]; 
            
            //Push root into the queue
            level.push_back(temp->key);
  
            // Push left child into the queue only if it`s not null
            if (temp->left != NULL) {
                queue[size++] = temp->left; 
             }

            // Push right child into the queue only if it`s not null
            if (temp->right != NULL) {
                queue[size++] = temp->right; 
             }
  
            // Increment the current index 
            index++; 
        } 
  
        //Calling the function which checks if a level is coPrime or not
        if (findGCD(level,level.size())==1 || level.size()==1) { 
          //A single number is always co-prime to itself

            printCoPrimeLevels(level); 
        } 
        //Clear the current level so as to
        // store the elements of the next level
        level.clear(); 
    } 
} 

 
int main(){ 
  
    //The tree we are creating below will look like this
         /*  10  
            /  \  
           48   6 
               /  \  
              18   37 
              / \  / \  
            21 29  43 16  
                      /  
                     7   */
                          
    Node* root = newNode(10); //Root node of the tree
    root->left = newNode(48); 
    root->right = newNode(6); 
  
    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); 
  
   //Function to find Co-Prime levels of a Binary Tree
   getCoPrimeLevels(root);
  
}

Output

10  
18 35 
21 29 43 16 
7

Leave a Reply