//C++ program to swap nodes in a binary tree of every kth level
#include<iostream>
#include <bits/stdc++.h>  
#include<queue>
using namespace std; 


template <typename T>//When the data is other than string then this template will be used
struct Value
{
   T data;
   Value()
   {
      data = 0;
   }
};

template <>	    //When the data is string then this template will be used
struct Value <string>
{
   string data;
   Value()
   {
      data.assign("");
   }
};

template <typename T>		//creating a new node
struct Node
{
   Value<T> data;
   Node<T>* left=nullptr;
   Node<T>* right=nullptr;
};


template <typename T>		//function template to create binary tree
Node<T>* createTree()
{
   //creating all nodes needed in the binary tree
   Node<T>* node1 = new Node<T>; 
   node1->data.data = 1;
   Node<T>* node2 = new Node<T>; 
   node2->data.data = 2;
   Node<T>* node3 = new Node<T>; 
   node3->data.data = 3;
   Node<T>* node4 = new Node<T>;
   node4->data.data = 4;
   Node<T>* node5 = new Node<T>; 
   node5->data.data = 5;
   Node<T>* node6 = new Node<T>; 
   node6->data.data = 6;
   Node<T>* node7 = new Node<T>; 
   node7->data.data = 7;
   Node<T>* node8 = new Node<T>; 
   node8->data.data = 8;
   Node<T>* node9 = new Node<T>; 
   node9->data.data = 9;
   Node<T>* node10 = new Node<T>; 
   node10->data.data = 10;
   
   //connecting nodes to create a binary tree
   node1->left = node2;
   node1->right = node3;
   node2->right = node4;
   node4->left = node5; 
   node4->right = node6;
   node3->left = node7;
   node7->right = node8;
   node8->left = node9;
   node8->right = node10;
   

   return node1;	//returning the root node as it is connected to every node
}


template <typename T>
void inorder(Node<T> *root)       //template to show inorder traversal of a binary tree
{ 
    if (root == NULL) 
        return; 
    inorder(root->left); 
    cout << root->data.data << " "; 
    inorder(root->right); 
} 

template <typename T>
void Swap( Node<T> **a , Node<T> **b)  //template to swap the nodes 
{ 
    Node<T> * temp = *a;   //creating a temp variable for swapping 
    *a = *b; 
    *b = temp; 
} 

template <typename T>
void kth_level( Node<T> *root, int level, int k)   //template to swap left and right node of the kth level

{
	if (root== NULL || (root->left==NULL && root->right==NULL) ) //base case
	        return ;
	if ( (level + 1) % k == 0)
		Swap(&root->left, &root->right); // calling the swapping function
	/*traversing the left and right node*/
    	kth_level(root->left, level+1, k);
    	kth_level(root->right, level+1, k);

}

int main() 
{ 
	Node<int>* root = createTree<int>();  //creating tree
	int k;
 	cout<<"Enter the value of k"<<endl;
	cin>>k;
    	cout << "Traversal Before swapping of nodes :"<<endl; 
    	inorder(root);  
  	kth_level(root,1,k);
	cout << "\nTraversal After swapping of nodes :" << endl; 
	inorder(root);
	cout<<endl; 
	return 0; 
} 

OUTPUT: