# Very Weird...What is wrong with my code

• Here is my code:

``````public class Solution {
public ArrayList<TreeNode> generateTrees(int n)
{
return helper(n,0);
}
public ArrayList<TreeNode> helper(int n,int k)
{
ArrayList<TreeNode> solution = new ArrayList<TreeNode>();
if(n==0)
{
TreeNode cu = null;
return solution;
}
else if(n==1)
{
TreeNode node = new TreeNode(n+k);
return solution;
}
else
{
for(int i=1;i<=n;i++)
{
ArrayList<TreeNode> a =  helper(i-1,k);
ArrayList<TreeNode> a2 = helper(n-i,i+k);
ArrayList<TreeNode> medium = new ArrayList<TreeNode>();
for(int j=0;j<a.size();j++)
{
TreeNode nd = new TreeNode(i+k);
nd.left = a.get(j);
}
for(int j=0;j<medium.size();j++)
{
for(int h=0;h<a2.size();h++)
{
TreeNode nd = medium.get(j);
nd.right = a2.get(h);
}
}
}
return solution;
}
}}
``````

The output is:
Input: 3
Output: [{1,#,3,2},{1,#,3,2},{2,1,3},{3,1,#,#,2},{3,2,#,1}]
Expected: [{1,#,2,#,3},{1,#,3,2},{2,1,3},{3,1,#,#,2},{3,2,#,1}]
Why {1,#,2,#,3} was replaced?

• Dang it Shangrila, I was working on that...

``````TreeNode nd = medium.get(j);
nd.right = a2.get(h);
}
``````

a2.get(j) returns the same node you just added to solution, and then you overwrite its right child, causing the one already in solution to change. By adding it into solution again, you have a doubled answer. The reason it works on {3,1,#,2} and {3,2,#,1} is because the pair of answers occur in the left subtree, so each gets their own node to be a child of.

If you merge the for loops, so you add left and right in the same section, you should get it to work.

for(int j=0;j<a.size();j++){
for(int h=0;h<a2.size();h++){
TreeNode nd=new TreeNode(i+k);
nd.left = a.get(j);
nd.right = a2.get(h);