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

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;

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=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```