# Java Tree Implementation

I wrote a simple tree data type in Java consisting of nodes which are themselves trees, and where each tree has its own list of children (not a binary tree). I plan on eventually using it in a minimax algorithm where I keep track of future game states in a board game by holding different board states in nodes and holding moves that lead to each state as edges in the tree. Here's my code so far — any suggestions (whether it be conceptual or performance related, or other features I should add) are appreciated:

public class Tree<V, E> {
private V data;
//here the edgeVal is the edge leading from the node's parent to the node itself,
//not from the node to any of its children
private E edgeVal;
private Tree<V, E> parent;
private ArrayList<Tree<V, E>> children;
public Tree(V data, Tree<V, E> parent, E edgeVal) {
this.data = data;
this.edgeVal = edgeVal;
this.parent = parent;
this.children = new ArrayList<Tree<V, E>>();
}
public void addChild(V childData, E edgeVal) {
Tree<V, E> child = new Tree<V, E>(childData, this, edgeVal);
}
public Tree<V, E> getParent() {
return this.parent;
}
public ArrayList<Tree<V, E>> getChildren() {
return this.children;
}
public V getData() {
return this.data;
}
public E getEdgeVal() {
return this.edgeVal;
}
public boolean isRoot() {
return this.parent == null;
}
public boolean isLeaf() {
return this.children.size() == 0;
}
public String toString() {
//assuming type of data has a nicely defined toString() method
return this.data.toString();
}
}

• I'm not an expert in game modelling, but I wonder if it is correct to assume the data structure is a tree. In some games a sequence of moves can lead to the same position. That leads to an infinite loop in a game and an infinite tree in strategy, which may be truncated by game rules (in chess, the same position for a third time ends the game) or may be not (I suppose, not all checkers variants do have such terminating rule). – CiaPan Mar 2 '16 at 7:59
• True if I were doing chess or checkers (I was a bit misleading when I said "board game") -- I'm actually using it for a game of Tron, where moving back to a space that you or your opponent has occupied makes you lose, so don't think I can hit an infinite loop. – Nick Mar 2 '16 at 8:12

Welcome to Code Review!

1. isLeaf compares the Size of children, a solution that is better readable is to use isEmpty() instead of compare the size of children.
2. The tree avoid a serialization that others may support, add the serializable-interface to keep serialization support.
3. edgeVal and data have no setter and to add final would help to avoid sideeffects whenever the code changes.

4. To have a ArrayList as a list of children has the problem that

• The ArrayList can contain null
• The ArrayList can contain one element twice (i do not think its a case you like to have)

You better use some kind of set, a LinkedHashSet in example.

5. You can use getChildren() to have read-write-access to the children, if you do oscar.getChildren().add(oscar); your loop is perfect but not a Tree. Use the unmodifyable-functions of the class Collections to return a readonly-collection.

6. The class is named Tree that can contains a list of Tree. Even if a Tree can be a parasite to other Trees i propose to name the Class TreeNode.

7. toString should describe the node, not the data inside.

8. Am i the only one who write javadoc?