Java - Indented list from a tree

Question

One of my university labs about trees has asked us to write a method called toIndentedString(). The description is the following:

Another way to represent the contents of a tree as a string is using an indented list. Here, we first represent the root, and then each of its child subtrees, indented by say two spaces (and this is applied recursively). For the example tree we would get:

food
  meat
    chicken
    beef
    fish
      salmon
      cod
      tuna
      shark
  fruit
  vegetable
    cabbage

Here's a diagram of the example tree:

Here is my current code:

package week10;

import java.util.*;

/**
 * Skeleton of the recursive implementation of a general tree.
 * 
 * @author Michael Albert
 * @param <T> The type of values stored in the tree.
 */
public class Tree<T> {

    private T rootValue;
    private List<Tree<T>> children;

    public Tree(T rootValue, List<Tree<T>> children) {
        this.rootValue = rootValue;
        this.children = children;
    }

    public Tree(T rootValue) {
        this(rootValue, new ArrayList<Tree<T>>());
    }

    public int size() {
        int count = 1;
        for (Tree<T> child : children) {
            count += child.size();
        }
        return count;
    }

    public int maxDegree() {
        // Get the number of immediate children
        int numChildren = this.children.size();

        // Find the max of all children
        int maxOfChildren = 0;
        for (Tree<T> child : children) {
            maxOfChildren = Math.max(maxOfChildren, child.maxDegree());
        }

        // return the greater of immediate child or max of children
        return Math.max(numChildren, maxOfChildren);
    }

    public void add(Tree<T> child) {
        children.add(child);
    }

    public Tree<T> find(T value) {
        if (rootValue.equals(value)) {
            return this;
        }
        for (Tree<T> child : children) {
            Tree<T> match = child.find(value);
            if (match != null) {
                return match;
            }
        }
        return null;
    }

    public List<T> postOrder() {
        ArrayList<T> list = new ArrayList<T>();
        for (Tree<T> child : children) {
            if (!child.children.isEmpty()) {
                child.postOrder();
            } else {
                //list.add(child);
                System.out.println(child);
            }
        }
        return list;
    }

    public String toString() {
        if (children.isEmpty()) {
            return rootValue.toString();
        }
        return rootValue.toString() + ' ' + children.toString();
    }

    public String toIndentedString() {
        // implement this method
        return "Not implemented yet!";
    }

    /** A helper method for testing (used by main).  Searches tree for
     *  the given target and adds white space separated children to
     *  the tree matching target if there is one.
     *
     * @param target the root value to seach for.
     * @param children a white space separated list of children to add
     * to the tree whose value matches target.
     */
    private static void addChildren(String target, String children) {
        Tree<String> parent = tree.find(target);
        if (parent != null) {
            for (String child : children.split(" ")) {
                parent.add(new Tree<>(child));
            }
        }
    }

    /** A tree instance used for testing. */
    private static Tree<String> tree;

    /**
     * Entry point of the program (used for testing).
     *
     * @param args command line arguments are not used.
     */
    public static void main(String[] args) {
        System.out.println("Creating tree\n-------------");
        tree = new Tree<>("food");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nAdding children\n----------------");
        addChildren("food", "meat fruit vegetable");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nAdding deeper children\n----------------------");
        addChildren("meat", "chicken beef fish");
        addChildren("fish", "salmon cod tuna shark");
        addChildren("vegetable", "cabbage");
        System.out.print(tree + "\nsize: " + tree.size());
        System.out.println(", max degree: " + tree.maxDegree());
        System.out.println("\nPostorder\n---------");
        System.out.println(tree.postOrder());
        System.out.println("\nIndented string\n---------------");
        System.out.print(tree.toIndentedString());
    }

}

How can I implement this method so that it recursively indents the subtrees?

Answer 1

Here's a simple recursive implementation:

public String toIndentedString() {
    StringBuilder sb = new StringBuilder(rootValue.toString());
    for (Tree<T> child : children) {
        sb.append('\n');
        sb.append(child.toIndentedString().replaceAll("(?m)^", "  "));
    }
    return sb.toString();
}

Ideone Demo

First, convert the root value to a string, and then add each of the child indented strings joined by newline characters. To indent each line of the child strings, use a replacement regex that adds an indentation to the front of every line.

Answer 2

Based on the example provided in your main method, you have a tree of String-nodes (your class is called "Tree" but the term "node" is more fitting for what they are).

As your assignment suggests, recursion is the key here. You'll want to traverse your tree nodes recursively, passing an increasing indentation level along with each recursive call. Something along these lines.

    private static final String INDENT_STRING = "  ";

    public String toIndentedString() {
        StringBuilder sb = new StringBuilder();
        this.buildIndentedString(sb, 0);
        return sb.toString();
    }

    private void buildIndentedString(StringBuilder builder, int indentationLevel) {
        for (int i = 0; i < indentationLevel; i++) {
            builder.append(INDENT_STRING);
        }
        builder.append(rootValue != null ? rootValue.toString() : "null");
        builder.append('\n');
        // Recurse over the children, building the tree with a deeper indentation level.
        for (Tree t : this.children) {
            t.buildIndentedString(builder, indentationLevel+1);
        }
    }

The recursive method buildIntentedString is where all the recursion happens. First, we append to the StringBuilder our indentation spacing. Then, we append the current node's object as a String (or "null" if we have a null object). Finally, we recurse: iterating over the current node's children and performing the same action with an increased indentation level. The output for your example should end up looking something like this:

food
  meat
    chicken
    beef
    fish
      salmon
      cod
      tuna
      shark
  fruit
  vegetable
    cabbage