I solved this challenge. It passes all the test cases, but I'm not very happy with my solution. I'm convinced this could be done much smoother (i.e less code)
Swap operation: Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].
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 inorder traversal of the current state of the tree.
Input Format: First line of input contains N, number of nodes in tree. Then N lines follow. Here each of ith line (1 <= i <= N) contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node. -1 is used to represent null node. Next line contain an integer, T. Then again T lines follows. Each of these line contains an integer K.
Here is my code:
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
int[][] leafs = new int[N][2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
leafs[i][j] = s.nextInt();
}
}
int[] depths = new int[s.nextInt()];
for (int i = 0; i < depths.length; i++) {
depths[i] = s.nextInt();
}
TreeNode leftTree = (leafs[0][0] > -1) ? new TreeNode(leafs[0][0]) : null;
TreeNode rightTree = (leafs[0][1] > -1) ? new TreeNode(leafs[0][1]) : null;
if (leafs[0][0] > -1) leftTree.mapChildNodes(leftTree, leafs, (leafs[0][0] > -1) ? 1 : 2, 0, N);
if (leafs[0][1] > -1) rightTree.mapChildNodes(rightTree, leafs, (leafs[0][0] > -1) ? 2 : 1, 0, N);
TreeNode mainTree = new TreeNode(1, leftTree, rightTree);
for(int d : depths) {
mainTree.swap(mainTree, d, 1);
mainTree.inorder(mainTree);
System.out.println();
}
}
}
class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
TreeNode(int data) {
this.data = data;
}
TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
private void insertLeft(int data) {
if (this.left == null) {
this.left = new TreeNode(data);
} else {
this.left.insertLeft(data);
}
}
private void insertRight(int data) {
if (this.right == null) {
this.right = new TreeNode(data);
} else {
this.right.insertRight(data);
}
}
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.toString());
inorder(node.right);
}
public void mapChildNodes(TreeNode node, int[][] leafs, int i, int j, int arraySize) {
if (arraySize == 0) return;
if (leafs[i][j] > -1){
node.insertLeft(leafs[i][j]);
mapChildNodes(node.left, leafs, leafs[i][j]-1, 0, arraySize-1);
}
if (leafs[i][j+1] > -1){
node.insertRight(leafs[i][j+1]);
mapChildNodes(node.right, leafs, leafs[i][j+1]-1, 0, arraySize-1);
}
}
public void swap(TreeNode node, int targetDepth, int depth) {
if(node == null) return;
if(depth % targetDepth == 0) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
swap(node.left, targetDepth, depth+1);
swap(node.right, targetDepth, depth+1);
}
@Override
public String toString() {
return this.data + " ";
}
}