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


hackerrank swap nodes algo solution


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;
        Queue queueA = new LinkedList();
        queueA.add(tree);
        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;
                queueA.add(left);
            }
            else
                temp.leftNode = null;

            value = s.nextInt();
            if(value != -1)
            {
                Tree right = new Tree();
                right.value = value;
                temp.rightNode = right;
                queueA.add(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)))