Inverse Alternative Binary Tree Levels

Question

Given an ideal binary tree, I need to change the alternating levels:

Given tree: a / \ bc / \ / \ defg / \ / \ / \ / \ hijklmno Modified tree: a / \ cb / \ / \ defg / \ / \ / \ / \ onmlkjih 

I am trying to use recursion to bypass a traversal and modify a tree in another workaround.

 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 pass the root of the reverseAltLevels () function, and from there I will call another function.

But I can’t understand exactly what the problem is with my code, I tried debugging in Eclipse, it seems good to me. Original crawl of the original:

 hdibjekalfmcngo 

Expected result after modification:

 odncmelakfjbigh 

My conclusion:

 odncmelalfmcngo 

Answer 1

Problem with your code

 list.add(node); 

The list now has the same reference to the source object.

In method

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

You are installing node data.

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

What causes the data to change inside the list of arrays.

to solve your problem. use Arraylist String to store only data, not to store Object itself