In this HackerRank Swap Nodes [Algo] interview preparation kit problem You are given a tree of n nodes where nodes are indexed from [1..n] and it is rooted at 1. You have to perform t swap operations on it and after each swap operation print the in-order traversal of the current state of the tree.

## Problem solution in Python programming.

```from collections import deque

class Node:
def __init__(self, index):
self.left = None
self.right = None
self.index = index

def in_order_traverse(root):
"""Don't use recursion b/c of recursion limit."""
stack = deque([root])
visited = set()
while stack:
node = stack.pop()
if node is None:
continue
if node.index in visited:
print(node.index, end=' ')
continue
stack.append(node.right)
stack.append(node)
stack.append(node.left)

def swap(root, k):
"""Don't use recursion b/c of recursion limit."""
q = deque([(root, 1)])
while q:
node, level = q.popleft()
if node is None:
continue
if level % k == 0:
node.left, node.right = node.right, node.left
q.append((node.left, level+1))
q.append((node.right, level+1))

# get number of nodes
N = int(input())

# create node list
nodes = [None]*(N+1)
for i in range(1, N+1):
n = Node(i)
n.left_index, n.right_index = [v if v > 0 else 0 for v in map(int, input().split())]
nodes[i] = n

# fill out node objects
for n in nodes[1:]:
left = nodes[n.left_index]
right = nodes[n.right_index]
n.left = left
n.right = right

T = int(input())
root = nodes[1]
# do the swapping
for _ in range(T):
k = int(input())
swap(root, k)
in_order_traverse(root)
print('')```

## Problem solution in Java Programming.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

import java.util.*;

public class Solution{
static Node root = new Node(1);

public static void main(String ... arg)
{
Scanner sc = new Scanner(System.in);
int n,t,k;
n = sc.nextInt();
int[][] tree = new int[n][2];
for(int i=0;i<n;i++)
{
tree[i][0] = sc.nextInt();
tree[i][1] = sc.nextInt();
}
root = ConstuctTree(tree);
t = sc.nextInt();
while(t-->0)
{
k = sc.nextInt();
levelWise(root,k);
InOrderRec(root);
System.out.println();
}
}

public static void levelWise(Node root,int k)
{
Stack<Node> currentlevel = new Stack<>();
Stack<Node> nextlevel = new Stack<>();
int level=1;
Node temp;
currentlevel.push(root);
while(!currentlevel.empty())
{
temp = currentlevel.peek();
currentlevel.pop();
if(temp.left!=null)
nextlevel.push(temp.left);
if(temp.right!=null)
nextlevel.push(temp.right);
if(level%k == 0)
{
Node n = temp.left;
temp.left = temp.right;
temp.right = n;
}
if(currentlevel.empty())
{
Stack<Node> t = currentlevel;
currentlevel = nextlevel;
nextlevel = t;
level++;
}
}
}

public static void InOrderRec(Node root)
{
if(root == null)
return;
InOrderRec(root.left);
sout(root.data);
InOrderRec(root.right);
}

public static Node ConstuctTree(int[][] tree)
{
Node root = new Node(1);
for(int i=0;i<tree.length;i++)
{
Node left,right;
if(tree[i][0]!=-1)
left = new Node(tree[i][0]);
else
left = null;
if(tree[i][1]!=-1)
right= new Node(tree[i][1]);
else
right = null;

Node temp = q.remove();
temp.left = left;
temp.right = right;

if(left!=null)
if(right!=null)
}
return root;
}

public static void sout(int info)
{
System.out.printf("%d ",info);
}
}

class Node{
int data;
Node left,right;
Node(int item)
{
data = item;
left = null;
right = null;
}
}```

### Problem solution in C++ programming.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> leftNode, rightNode;
int swapLevel;

void traverse(int node=1){
if (node == -1) return;
traverse(leftNode[node]);
cout << node << " ";
traverse(rightNode[node]);
if (node == 1) cout << endl;
}

void swap(int level=1, int node=1) {
if (node == -1) return;
if (level % swapLevel == 0) {
int tmp = leftNode[node];
leftNode[node] = rightNode[node];
rightNode[node] = tmp;
}
swap(level+1, leftNode[node]);
swap(level+1, rightNode[node]);
}

int main() {
int count;
cin>>count;
leftNode.push_back(0);
rightNode.push_back(0);
while(count--){
int L, R;
cin>>L>>R;
leftNode.push_back(L);
rightNode.push_back(R);
}
cin>>count;
while(count--){
cin >> swapLevel;
swap();
traverse();
}
return 0;
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node {
int data;
struct node *left;
struct node *right;
};

struct node* create_node(int val){
if(val == -1){
return NULL;
}
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=val;
temp->left=NULL;
temp->right=NULL;
return temp;
}

void inorder(struct node *root){
if(!root){
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

int max(int a, int b){
if(a>b){
return a;
} else {
return b;
}
}

int height(struct node * root){
if(!root){
return 0;
}
return(1+max(height(root->left),height(root->right)));
}

void swap_nodes_at_level(struct node *root, int inc, int level, int height){
struct node *tnode;
if(!root){
return;
}
if(level > height){
return;
}
if(!(level%inc)){
tnode=root->left;
root->left=root->right;
root->right=tnode;
}
swap_nodes_at_level(root->left, inc, level+1, height);
swap_nodes_at_level(root->right, inc, level+1, height);
}

int tail=0;

void enqueue(struct node **queue, struct node *root){

queue[tail]=root;
tail++;
}

struct node* dequeue(struct node **queue){

return temp;
}

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int nodes_count, i, temp, h, tc_num, index, inc, temp1, temp2;

scanf("%d", &nodes_count);

//  printf("%d\n", nodes_count);

// int arr[2*nodes_count+1];

struct node *root_perm, *root_temp;

//queue=create_queue(nodes_count);

struct node *q[nodes_count];
for(i=0;i<nodes_count;i++){
q[i]=NULL;
}

//building the array

//arr[0]=1;

// for(i=1;i<=2*nodes_count;i++){
//   scanf("%d",&temp);
//  arr[i]=temp;
//   printf("%d ", arr[i]);
// }

i=0,index=1;
root_temp=root_perm=create_node(1);
enqueue(q, root_temp);

while(index<=2*nodes_count) {

//printf("\n In Loop : i : %d",i);
root_temp=dequeue(q);
//setting up the left child
scanf("%d", &temp1);
if(temp1 == -1){

} else {
root_temp->left=create_node(temp1);
enqueue(q, root_temp->left);
}
//setting up the right child
scanf("%d", &temp2);
if(temp2==-1) {

} else {
root_temp->right=create_node(temp2);
enqueue(q, root_temp->right);
}
index=index+2;
//  i++;

}

h = height(root_perm);

scanf("%d", &tc_num);

//printf("%d",tc_num);
//printf("\n");

//inorder(root_perm);

while(tc_num){
scanf("%d",&inc);
temp=inc;
//while(temp < height){
swap_nodes_at_level(root_perm, inc, 1, h);
//temp=temp + inc;
//}
//temp=0;
inorder(root_perm);
printf("\n");
tc_num--;
}

//Tree is created at this point

return 0;
}```

### Problem solution in JavaScript programming.

```function toNumber (arr) { return arr.map(function (i) { return Number(i); })}

function nodesAtDepth(root, depth, current) {
current = current || 1;
if (depth === current) {
return [root];
} else {
return (
[].concat(root.left ? nodesAtDepth(root.left, depth, current + 1) : [])
.concat(root.right ? nodesAtDepth(root.right, depth, current + 1) : []));
}
}

function inOrderTraversal(root) {
var out = [];
if (root.left) out = out.concat(inOrderTraversal(root.left));
out.push(root.val);
if (root.right) out = out.concat(inOrderTraversal(root.right));
return out;
}

function TNode(v, l, r) {
this.val = v;
this.right = r || undefined;
this.left = l || undefined;
}

TNode.prototype.swap = function () {
tmp = this.right;
this.right = this.left;
this.left = tmp;
}

function swap(root, k, max) {
var d = k, i = 2;
while (d <= max) {
nodesAtDepth(root, d, 1).forEach(function (node) { node.swap(); });
d = i * k;
i++;
}
console.log(inOrderTraversal(root).join(' '));
}

function processData(input) {

var lines = input.split('\n').reverse();

var n = Number(lines.pop().split());
var nodes = new Array(n+1);

var _index, _lr, i, k;

for (i = 0; i < n ; i++) {
_index = i + 1;
nodes[_index] = new TNode(_index);
}

for (i = 0; i < n ; i++) {
_index = i + 1;
_lr = toNumber(lines.pop().split(' '));
if (_lr[0] > -1) nodes[_index].left = nodes[_lr[0]];
if (_lr[1] > -1) nodes[_index].right = nodes[_lr[1]];
}

var ops = Number(lines.pop());
for (var j = 0; j < ops; j++) {
k = Number(lines.pop()) ;
swap(nodes[1], k, n - 1);
}

}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});```