Binary Tree Node values change after adding them to ArrayList

Question

First of all, I´m aware of having to create a new Tree instance in every iteration as not to reuse the same object and also having static objects as this and this threads inform.I think I´ve checked every part of the code for that.

So, I am testing the code below. A bit of information on what it does:

The first loop iterates over a List of Root nodes with children forming a binary tree. I create a tree object for every root node and add it to it, the object also contains two arraylist one for all nodes in the tree and another for just the leaves. In the loop I also set numbers randomly to every leaf in every tree from 1 to n (where n is the number of leafs in the tree) and add the tree to an arrayList : possibleTrees.

Problem: In the first loop when I iterate over the leaves of every tree and print their numbers it prints them accordingly. But after it finishes and I iterate over possibleTrees printing all tree´s leaves, many values change.

Here´s the code and the output below it for a tree with 4 leaves. The top part prints twice because one is an arraylist of integers and the second one is printing the values directly from the nodes

Edit: Link to Tree,Node classes

Edit2 : added alltopologies class (http://) pastebin.com/sB9UV8T6

    ArrayList<Tree> possibleTrees = new ArrayList<Tree>();
    ArrayList<Integer> numbers = new ArrayList<Integer>();        
    for (int i = 0; i < numNodes; i++) {
        numbers.add(i + 1);
    }
    for (Node n : allTopologies.allBinaryTrees(numNodes)) {
        Tree tree = new Tree();

        tree.setNodesLists(n);

        Collections.shuffle(numbers);
        tree.setleafNums(n, numbers);
        tree.setRoot(n);

        possibleTrees.add(tree);

        System.out.println(numbers);
        System.out.print("[");
        for (Node l : tree.getLeaves()) {

            System.out.print(l.getLeafNum() + ", ");
        }
        System.out.println("]");
        System.out.println("");

    }
    System.out.println("-------------------------------");
    for (Tree t : possibleTrees) {
        System.out.print("[");
        for (Node l : t.getLeaves()) {

            System.out.print(l.getLeafNum() + ", ");
        }
        System.out.println("]");
        System.out.println("");
    }

OutPut:
[3, 2, 1, 4] [3, 2, 1, 4, ]

[2, 4, 1, 3] [2, 4, 1, 3, ]

[1, 3, 2, 4] [1, 3, 2, 4, ]

[3, 4, 2, 1] [3, 4, 2, 1, ]

[2, 2, 1, 4, ]

[2, 4, 1, 3, ]

[1, 3, 2, 1, ]

[3, 4, 2, 1, ]

Thanks in advance !

There’s gotta be an explanation somewhere. I haven’t yet found it in the code you have posted. See if you can reproduce the unwanted behaviour in a [Minimal, Complete, and Verifiable example](http://stackoverflow.com/help/mcve). — Ole V.V., Aug 27 '16 at 19:32
I still cannot compile your code - too much is missing. However, part of your problem might be the method `Node.isExternal()` - it returns true if it has zero children or if it has one child node. — Thomas Kläger, Aug 27 '16 at 20:51
@OleV.V. I did try to leave out as much code as possible and I had a thought that It might be the Collections.shuffle part but I haven´t been able to verify it. — Enixf, Aug 28 '16 at 01:57
@ThomasKläger I added the parts of the code that are missing, I think you can now try and compile it. I had to put third link in parenthesis because I couldn´t post it. Also, I don´t think that´s the problem, switching from an OR to an AND wouldn´t make a difference here since the only nodes without children are leaves. — Enixf, Aug 28 '16 at 02:01
I’ve compiled your CreateAlTopologies class, but neither Tree, Node nor the snippet in the question (I pasted it into a main method). Just to give one example, you are calling `tree.setRoot()`, but your `Tree` class does not define a `setRoot` method. There are many other problems. — Ole V.V., Aug 28 '16 at 06:22
I’m thinking, the two obvious explanations are (1) the content of a node has been changed (2) you don’t get the same node objects the second time. For (1), you are printing the leaves’ `getLeafNum()`, but (a) there is no such method in your node class, (b) there is nothing in your code ever putting any value into the `leafNum` field. For (2), you are getting the leaves from a `getLeaves` method, but you have not provided the code of that method, so we have no way of helping with what it returns. — Ole V.V., Aug 28 '16 at 06:36
I suggest you try using a debugger. You may stumble on an error quickly or you may be facing a greater task, I cannot tell. In your debugger, first try to see if you get the same node objects both times (most debuggers show an internal object ID). — Ole V.V., Aug 28 '16 at 06:39
@OleV.V. damn, I´m very sorry. I should have pasted the imports too. The thing is I´m using a library called Lombok that autogenerates those methods and I don´t have to worry about those. I just have been using it for so long that I forgot is not included. — Enixf, Aug 28 '16 at 11:13

Thomas Kläger · Accepted Answer · 2016-08-28T07:11:57.940

1

For your algorithm to work your tree must not share nodes.

However in the inner loop of allBinaryTrees(), you create trees with shared nodes:

    for (Node lt : possibleLeftSubtrees) {
        for (Node rt : possibleRightSubtrees) {
            // make a tree of a node with lt and rt as subtrees,
            // and add it to the result
            result.add(new Node(i,lt, rt));
        }
    }

If possibleLeftSubtrees has one node and possibleRightSubtrees has two nodes, you create two resulting trees that share the left node.

By the way, your Tree.clone() method is broken:

Node b = new Node(2);
Node a = new Node(1, b, null);
b.setParent(a);
System.out.println(a.clone());

will raise a StackOverflowError, since cloning a means cloning its left child b which means cloning its parent a which means... add infinitum.

edited Aug 28 '16 at 07:11

answered Aug 28 '16 at 06:51

Thomas Kläger

17,754
3
23
34

Da**, I provided the broken code in another question. I didn’t know back then it was a requirement not to reuse nodes, but I should have been aware that it potentially entailed problems. Sorry I didn’t warn you. – Ole V.V. Aug 28 '16 at 12:01
I thought it might be this, but since I created a new node for every leaf I thought it wasn´t a problem. Any suggestion as how to create each node separately but achieve the same result ? Thanks for the clone tip btw – Enixf Aug 28 '16 at 12:12
Obvious in my mind: in the code that @ThomasKläger quotes, make deep copies of `lt` and `rt` and pass the copies to the `new Node()`. – Ole V.V. Aug 28 '16 at 12:23
Thanks guys, it works now by making individual nodes for each tree! – Enixf Aug 28 '16 at 17:02

Binary Tree Node values change after adding them to ArrayList

1 Answers1