String representation of Tree

Question

I have a Tree class, defined as follows:

public class Tree<T> {
    private T value;    
    protected List<Tree<T>> children = new ArrayList<Tree<T>>();
    /* ... */
}

I want to implement the toString() method in this class to show the String representation of this Tree, e.g.:

└── root
    ├── child1
    │   └── grandchild1
    └── child2

I implemented in this way:

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    buildString(sb, "", true);
    return sb.toString();
}

private void buildString(StringBuilder sb, String prefix, boolean isTail) {
    sb.append(isTail ? "└── " : "├── ").append(value).append(System.lineSeparator());
    prefix = prefix + (isTail ? "    " : "│   ");

    for (int i = 0; i < children.size() - 1; i++) {
        sb.append(prefix);
        children.get(i).buildString(sb, prefix, false);
    }
    if (children.size() >= 1) {
        sb.append(prefix);
        children.get(children.size() - 1).buildString(sb,prefix, true);
    }
}

I am looking for possible improvements or suggestions.

Answer 1

Some suggestions (by far not complete as the other answer(s) show):

• You don't need to specify the type twice:

  protected List<Tree<T>> children = new ArrayList<Tree<T>>();
  protected List<Tree<T>> children = new ArrayList<>();
  

• Create a new parameter maxDepth to limit the function nesting level.
  It should be set to a default value to follow the principle of least astonishment: Nobody would expect his program to crash just because he triggered the string conversion somehow.

• With very big trees the nested function calls can become a problem.
  But I wouldn't worry about it for two reasons:

  • The function is not named archiveTree. As a user, I wouldn't expect it to handle each and every scenario of a tree.
  • The default value maxDepth should reasonably prevent out of memory scenarios as long as the user doesn't manually provide disproportional values. If he does, it's his fault and not yours anymore.
    

• You sometimes have inconsistent spacing, e.g.:

  buildString(sb,prefix, true);
  buildString(sb, prefix, true);
  

• You could specify the capacity argument with a guessed value to the constructor of StringBuilder to prevent some unnecessary capacity allocations. However, as long as you haven't identified this as a noticeable bottleneck of your application, I would consider it to be premature optimization.

Answer 2

Consider this code:

Tree t = new Tree("Hi");
Tree e = new Tree("Hi");
t.getChildren().add(e); 
e.getChildren().add(t);
System.out.println(t); 

Will give you a RuntimeException because you built a loop.

Practice problems:

1. Naming: The class named Tree but actually is a Node.
2. This Node by definition of the method toString() should

   ...return a string "textually represents" this Node.

3. The Single-Responsibility-Principle is a practice that its not the responsibility of the leaf to print the whole tree. You better create a TreeView with the responsibility to display.

I can not give you a concrete example because I do not know if you need a loop-scanner or a maximum-deepnes(as ComFreek suggested) or anything.