Reverse alternate levels of a binary tree

Question

Given a perfect binary tree I need to reverse alternating levels:

Given tree: 
           a
        /     \
       b       c
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
   h  i j  k l  m  n  o 

Modified tree:
           a
        /     \
       c       b
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
  o  n m  l k  j  i  h 

I am trying to use recursion to do a inorder traversal and modify the tree in another inorder traversal.

public static void reverseAltLevels(TreeNode node) {
    if (node == null)
        return;
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    storeAltNodes(node, list, 0);

    Collections.reverse(list);
    System.out.println();
    for (TreeNode n : list)
        System.out.print(n.data + " ");
    modifyTree(node, list, 0, 0);
}

public static void storeAltNodes(TreeNode node, ArrayList<TreeNode> list,
        int level) {
    if (node == null)
        return;
    storeAltNodes(node.left, list, level + 1);
    if (level % 2 != 0) {
        list.add(node);
    }
    storeAltNodes(node.right, list, level + 1);
}

public static int modifyTree(TreeNode node, ArrayList<TreeNode> list,
        int index, int level) {
    if (node == null)
        return index;
    index = modifyTree(node.left, list, index, level + 1);
    if (level % 2 != 0) {
        node.data = list.get(index).data;
        index++;
    }
    index = modifyTree(node.right, list, index, level + 1);
    return index;
}

public static void inOrder(TreeNode node) {
    if (node == null)
        return;
    inOrder(node.left);
    System.out.print(node.data + " ");
    inOrder(node.right);
}

I will be passing the root to the reverseAltLevels() function and from there I will be calling the other func.

But I am not able figure out the exact problem with my code, tried debugging in Eclipse, seems OK to me. Original Inorder traversal:

h d i b j e k a l f m c n g o 

Expected Result after modification:

o d n c m e l a k f j b i g h

My Output:

o d n c m e l a l f m c n g o 

Answer 1

The problem with your code is

list.add(node);

Now the list has the same reference to the original Object

In the method

public static int modifyTree(TreeNode node, ArrayList<TreeNode> list,
            int index, int level)

you are setting the nodes data.

node.data = list.get(index).data;

Which causes the modification of the data inside the array list.

for solving your problem. use Arraylist of String to Store just the data, rather than storing the Object itself