Swap nodes in a binary tree

Question

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 + " "; 
    }
}

Answer 1

Current solution

There's nothing really wrong with your current solution. You build the tree, do the swapping and then do the inorder traversal. Each step is implemented in a simple way and there isn't much excess code. However, since you asked about doing it in less code, I will show you two ways to dramatically reduce your code.

You don't need to build a second tree

If you think about it, after you have read in the tree into your array called leafs, you already have a complete tree structure. You don't need to build a second tree with nodes, left/right children, etc. You can just use the array as your tree representation. Therefore, all of your TreeNode code is unnecessary.

You can print the inorder traversal during the swap

Right now, you run the swap() function to swap the requested nodes, and then run the inorder() function to print the nodes in the swapped tree. Since those are the only two operations you need to do, you can just print the traversal while swapping instead of doing two passes.

Revised solution

Here is what your code would look like after making the above two changes. Note that I modified the array to be 1-based because the problem wanted the root to be node 1.

import java.util.Scanner;

public class Solution {
    public static final int ROOT_NODE = 1;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        final int N = s.nextInt();
        int[][] tree = new int[N+ROOT_NODE][2];

        for (int i = ROOT_NODE; i < N+ROOT_NODE; i++) {
            for (int j = 0; j < 2; j++) {
                tree[i][j] = s.nextInt();
            }
        }

        int numDepths = s.nextInt();
        for (int i = 0; i < numDepths; i++) {
            swap(tree, ROOT_NODE, s.nextInt(), 1);
            System.out.println();
        }
    }

    public static void swap(int [][] tree, int node, int targetDepth,
            int depth) {
        if(node == -1) return;

        if(depth % targetDepth == 0) {
            int temp = tree[node][0];
            tree[node][0] = tree[node][1];
            tree[node][1] = temp;
        }
        swap(tree, tree[node][0], targetDepth, depth+1);
        System.out.print(Integer.toString(node) + " ");
        swap(tree, tree[node][1], targetDepth, depth+1);
    }
}