«
»

, , ,

A recursive toString method for trees

Friday, January 30th, 2009 - 11:02 pm - Java

While working on a project that uses Hibernate, my team was getting a little frustrated while trying to interrogate a tree structure in our data model since all collections are mapped as java.util.HashSets.  We wanted a simple function that could print the tree to the log, so I took a free hour and wrote this.  It was a little more complicated than I anticipated because it had to handle situations like these.

root
   |
   |- child
   |
   |- child

root
   |
   |- child
      |
      |- child

and the infamous (to me) …

root
   |
   |- child
   |   |
   |   |- child
   |       |
   |       |- child
   |
   |- child

There’s a subtle difference.  Notice that in the middle one, the line for the first child stops because there aren’t any more children, but in the last one, the line continues?  I could have created some kind of 2D text buffer and gone back to draw the line, but that would be boring.  Here’s what I came up with. I don’t know whether it’s pretty, but it works!

/**
 * Creates a tree representation of the node
 * @param node The node, which may not be null
 * @return A string containing the formatted tree
 */
public static String toStringTree(Node node) {
  final StringBuilder buffer = new StringBuilder();
  return toStringTreeHelper(node, buffer, new LinkedList<Iterator<Node>>()).toString();
}
 
private static void toStringTreeDrawLines(List<Iterator<Node>> parentIterators, boolean amLast) {
  StringBuilder result = new StringBuilder();
  Iterator<Iterator<Node>> it = parentIterators.iterator();
  while (it.hasNext()) {
    Iterator<Node> anIt = it.next();
    if (anIt.hasNext() || (!it.hasNext() && amLast)) {
      result.append("   |");
    }
    else {
      result.append("    ");
    }
  }
  return result.toString();
}
 
private static StringBuilder toStringTreeHelper(Node node, StringBuilder buffer, List<Iterator<Node>>
    parentIterators) {
  if (!parentIterators.isEmpty()) {
    boolean amLast = !parentIterators.get(parentIterators.size() - 1).hasNext();
    buffer.append("\n");
    String lines = toStringTreeDrawLines(parentIterators, amLast);
    buffer.append(lines);
    buffer.append("\n");
    buffer.append(lines);
    buffer.append("- ");
  }
  buffer.append(node.toString());
  if (node.hasChildren()) {
    Iterator<Node> it = node.getChildNodes().iterator();
    parentIterators.add(it);
    while (it.hasNext()) {
      Node child = it.next();
      toStringTreeHelper(child, buffer, parentIterators);
    }
    parentIterators.remove(it);
  }
  return buffer;
}