Function Description

Complete the swapNodes function in the editor below. It should return a two-dimensional array where each element is an array of integers representing the node indices of an in-order traversal after a swap operation.

swapNodes has the following parameter(s):
indexes: an array of integers representing index values of each , beginning with , the first element, as the root.
queries: an array of integers, each representing a  value.

Input Format
The first line contains n, number of nodes in the tree.

Each of the next n lines contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node.

Note: -1 is used to represent a null node.

The next line contains an integer, t, the size of .
Each of the next t lines contains an integer , each being a value .

Output Format
For each k, perform the swap operation and store the indices of your in-order traversal to your result array. After all swap operations have been performed, return your result array for printing

## Problem solution in C++ programming language.

#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 language.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node
{
int left;
int right;
};
int depth(struct node* arr, int i)
{
if(i==-1)
{
return 0;
}

int left  = depth(arr,arr[i].left);
int right = depth(arr,arr[i].right);

if(left>right)
{
return (left+1);
}
else return (right+1);

}

void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}

void swapNode(struct node * arr,int i, int level,int k)
{
if(i==-1)
{
return;
}
else
{
if(level==k)
{
swap(&arr[i].left,&arr[i].right);
return;
}
else if(level<k)
{
level++;
swapNode(arr,arr[i].left,level,k);
swapNode(arr,arr[i].right,level,k);
}
}
}

void inorder(struct node * arr, int i)
{
if(i==-1)
{
return;
}
else
{
inorder(arr,arr[i].left);
printf("%d ",i);
inorder(arr,arr[i].right);
}
}
int main()
{
int t,N,i,j,k;
scanf("%d",&N);
//printf("%d\n",N);
struct node *arr = (struct node *)malloc(sizeof(struct node) *(N+1));
for(i=1;i<=N;i++)
{
scanf("%d%d",&arr[i].left,&arr[i].right);
// printf("%d%d\n",arr[i].left,arr[i].right);
}
int dep = depth(arr,1);
// printf("dpth :%d\n",dep);
scanf("%d",&t);
// printf("%d\n",t);
while(t--)
{
scanf("%d",&k);
int temp=k;
j=1;
while(temp<= dep)
{
swapNode(arr,1,1,temp);
j++;
temp = k*j;
}
inorder(arr,1);
printf("\n");

}

return 0;
}

### Problem solution in Java programming language.

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner s = new Scanner(System.in);
int n = s.nextInt();
Tree tree = new Tree();
tree.value = 1;
while(!queueA.isEmpty())
{
Tree temp = (Tree)queueA.remove();
int value = s.nextInt();
if(value != -1)
{
Tree left = new Tree();
left.value = value;
temp.leftNode = left;
}
else
temp.leftNode = null;

value = s.nextInt();
if(value != -1)
{
Tree right = new Tree();
right.value = value;
temp.rightNode = right;
}
else
temp.rightNode = null;
}
int t = s.nextInt();
for(int i=0;i<t;i++)
{
int k = s.nextInt();
swapTree(tree,k,0,1);
inorder(tree);
System.out.println();
}
}

private static void inorder(Tree t)
{
if (t == null)
return;
inorder(t.leftNode);
System.out.print(t.value+" ");
inorder(t.rightNode);
}

private static void swapTree(Tree t,int k, int cur,int mul)
{
if (t == null)
return;
cur++;
if(cur == (mul*k))
{
Tree temp = t.leftNode;
t.leftNode = t.rightNode;
t.rightNode = temp;
++mul;
swapTree(t.leftNode, k, cur,mul);
swapTree(t.rightNode, k, cur,mul);
}
else
{
swapTree(t.leftNode, k, cur,mul);
swapTree(t.rightNode, k, cur,mul);
}
}
}

class Tree{
int value;
Tree leftNode;
Tree rightNode;
}

### Problem solution in Python programming language.

def inorder(T) :
stack = [1]
result = []
while stack :
i = stack.pop()
if i > 0 :
if T[i][1] > 0 :
stack.append(T[i][1])
stack.append(-i)
if T[i][0] > 0 :
stack.append(T[i][0])
else :
result.append(-i)
return result

def swap(T, K) :
toVisit, depth = [1], 1
while toVisit :
if depth % K == 0 :
for i in toVisit :
T[i] = (T[i][1], T[i][0])
toVisit_ = []
for i in toVisit :
if T[i][0] > 0 :
toVisit_.append(T[i][0])
if T[i][1] > 0 :
toVisit_.append(T[i][1])
toVisit = toVisit_
depth += 1

N = int(input())
T = [None] + [tuple(int(_) for _ in input().split()) for _ in range(N)]

N = int(input())
for _ in range(N) :
swap(T,int(input()))
print(" ".join(str(_) for _ in inorder(T)))