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[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