## Algorithm

Problem Name: Data Structures - Swap Nodes [Algo]

In this HackerRank in Data Structures - Swap Nodes [Algo] solutions

A binary tree is a tree which is characterized by one of the following properties:

• It can be empty (null).
• It contains a root node only.
• It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees.

In-order traversal is performed as

1. Traverse the left subtree.
2. Visit root.
3. Traverse the right subtree.

For this in-order traversal, start from the left child of the root node and keep exploring the left subtree until you reach a leaf. When you reach a leaf, back up to its parent, check for a right child and visit it if there is one. If there is not a child, you've explored its left and right subtrees fully. If there is a right child, traverse its left subtree then its right in the same manner. Keep doing this until you have traversed the entire tree. You will only store the values of a node as you visit when one of the following is true:

• it is the first node visited, the first time visited
• it is a leaf, should only be visited once
• all of its subtrees have been explored, should only be visited once while this is true
• it is the root of the tree, the first time visited

Swapping: Swapping subtrees of a node means that if initially node has left subtree L and right subtree R, then after swapping, the left subtree will be R and the right subtree, L.

For example, in the following tree, we swap children of node 1.

                                Depth
1               1            [1]
/ \             / \
2   3     ->    3   2          [2]
\   \           \   \
4   5           5   4        [3]


In-order traversal of left tree is 2 4 1 3 5 and of right tree is 3 5 1 2 4.

Swap operation:

We define depth of a node as follows:

• The root node is at depth 1.
• If the depth of the parent node is d, then the depth of current node will be d+1.

Given a tree and an integer, k, in one operation, we need to swap the subtrees of all the nodes at each depth h, where h ∈ [k, 2k, 3k,...]. In other words, if h is a multiple of k, swap the left and right subtrees of that level.

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.

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 node[i] , beginning with node[1] the first element, as the root.
- queries: an array of integers, each representing a k 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 queries

Each of the next t lines contains an integer queries[i], each being a value k.

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.

Constraints

• 1 <= n <= 1024
• 1 <= t <= 100
• 1 <= k <= n
• Either a = -1 or 2 <= a <= n
• Either b = -1 or 2 <= b <= n
• The index of a non-null child will always be greater than that of its parent.

Sample Input 0

3
2 3
-1 -1
-1 -1
2
1
1


Sample Output 0

3 1 2
2 1 3


Explanation 0

As nodes 2 and 3 have no children, swapping will not have any effect on them. We only have to swap the child nodes of the root node.

    1   [s]       1    [s]       1
/ \      ->   / \        ->  / \
2   3 [s]     3   2  [s]     2   3


Note: [s] indicates that a swap operation is done at this depth.

Sample Input 1

5
2 3
-1 4
-1 5
-1 -1
-1 -1
1
2


Sample Output 1

4 2 1 5 3


Explanation 1

Swapping child nodes of node 2 and 3 we get

    1                  1
/ \                / \
2   3   [s]  ->    2   3
\   \            /   /
4   5          4   5


Sample Input 2

11
2 3
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4


Sample Output 2

2 9 6 4 1 3 7 5 11 8 10
2 6 9 4 1 3 7 5 10 8 11


Explanation 2

Here we perform swap operations at the nodes whose depth is either 2 or 4 for K = 2 and then at nodes whose depth is 4 for K = 4

.

         1                     1                          1
/ \                   / \                        / \
/   \                 /   \                      /   \
2     3    [s]        2     3                    2     3
/      /                \     \                    \     \
/      /                  \     \                    \     \
4      5          ->        4     5          ->        4     5
/      / \                  /     / \                  /     / \
/      /   \                /     /   \                /     /   \
6      7     8   [s]        6     7     8   [s]        6     7     8
\          / \            /           / \              \         / \
\        /   \          /           /   \              \       /   \
9      10   11        9           11   10              9     10   11


## Code Examples

### #1 Code Example with C Programming

Code - 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;
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - 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;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - 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 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);
Queue < Node> q = new LinkedList<>();
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;
}
}

Copy The Code &

### #4 Code Example with Javascript Programming

Code - 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);
});

Copy The Code &

### #5 Code Example with Python Programming

Code - 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('')

Copy The Code &