Converting tree structure to 2d 'grid' array in java

Question

I'm trying to display a tree structure in a table, and can't quite get my head around the last bit.

I have a fairly standard node class (with methods and constructors removed for clarity),

public class TreeNode<T> {

    private TreeNode<?>         parent;
    private T                   data;
    private List<TreeNode<?>>   children    = new ArrayList<>();

}

which might be populated something like this:

TreeNode<String> grandchild1 = new TreeNode<>("Grandchild 1");
TreeNode<String> grandchild2 = new TreeNode<>("Grandchild 2");
TreeNode<String> grandchild3 = new TreeNode<>("Grandchild 3");
TreeNode<String> child1 = new TreeNode<>("Child 1");
child1.addChild(grandchild1);
child1.addChild(grandchild2);
TreeNode<String> child2 = new TreeNode<>("Child 2");
child2.addChild(grandchild3);
TreeNode<String> root = new TreeNode<>("Root");
root.add(child1);
root.add(child2);

In order to print this data in a table, I would like to populate a nested List structure as follows,

[["Root", "Child 1", "Grandchild 1"],
 ["", "", "Grandchild 2"],
 ["", "Child 2", "Grandchild 3"]]

so that the data is 'flattened', and not repeated, so I will later be able to print it in a table like this:

| Root   | Child 1    | Grandchild 1 |
|        |            | Grandchild 2 |
|        | Child 2    | Grandchild 3 |

Here's what I've tried so far:

public List<List<String>> getData(TreeNode<?> root) {
    List<List<String>> data = new ArrayList<>();
    getData(data, root);
    return data;
}

private void getData(List<List<String>> data, TreeNode<?> node) {
    if (!node.isLeaf()) {
        for (TreeNode<?> child : node.getChildren()) {
            getData(data, child);
        }
    } else {
        data.add(getRow(currentNode));
    }
}

private List<String> getRow(TreeNode<?> node) {
    Deque<String> row = new LinkedList<>();
    TreeNode<?> currentNode = node;
    while (!currentNode.isRoot()) {
        row.addFirst(String.valueOf(currentNode.getData()));
        currentNode = currentNode.getParent();
    }
    return new ArrayList<>(row);
}

Although this recursively collects the data to display, obviously the data will be repeated as for each row it's parent value is printed, and I will end up with this:

[["Root", "Child 1", "Grandchild 1"],
 ["Root", "Child 1", "Grandchild 2"],
 ["Root", "Child 2", "Grandchild 3"]]

What I'm struggling with is a way to decide if a certain value should be printed (repeated) or not, as I'm sure there must be an elegant solution.

There are no guarantees on the size or structure of the tree so the most generic solution would be the best. Any help would be greatly appreciated!

Answer 1

Thanks to P. van der Laan I was able to come up with a rather un-elegant solution. If there is a better or more 'standard' way to achieve this I would love to hear it!

So I made a class to hold the nested list and the current row position:

public class NodeGrid {

    private List<List<String>>  data        = new ArrayList<>();
    private int                 currentRow  = 0;

    public void addData(String dataString) {
        while (data.size() <= currentRow) {
            data.add(new ArrayList<>());
        }
        data.get(currentRow).add(dataString);
    }

    public void newRow() {
        data.add(new ArrayList<>());
        currentRow++;
    }

    public List<List<String>> getData() {
        data.remove(currentRow); // the last row is deleted before retrieving since it will always be empty
        return data;
    }
}

Which can then implement the DFS in the same way:

private void getRowData(NodeGrid data, TreeNode<?> currentNode, int depth) {
    if (currentNode.isLeaf()) {
        data.addData(String.valueOf(currentNode.getData()));
        data.newRow();
    } else {
        data.addData(String.valueOf(currentNode.getData()));
        getRowData(data, currentNode.getChild(0), depth + 1);
        for (int i = 1; i < currentNode.getChildren().size(); i++) {
            for (int d = 0; d < depth + 1; d++) {
                data.addData("");
            }
            getRowData(data, currentNode.getChild(i), depth + 1);
        }
    }
}

I'm not convinved this is the best solution, and it doesn't seem very efficient either (having to remove the last added empty line), but it works for now.

Answer 2

Traversing the same as the answer of @Matteo Ugolotti, just a different trailing depth and leading node print.

For each node, print all children on the same line recursively. When the line is print, each child (if any) of the just printed nodes is recursively printed too.

The columns have a max column that is used to get all nodes printed as straight columns. It should be at least as big as the largest node data.

I removed the generics and made each node String to be able to get the length of each node (used to correctly print columns). You could create a method in your Node class that returns the length of the (generic) data.

public void printTree(Node<String> node, int depth, int columnSize) {
    // Print leaf
    if(node.children.size() == 0) {
        printNode(node, columnSize);
        System.out.print("|\n");
    } else {
        // Print current node
        printNode(node, columnSize);

        // Print all nodes of this level recursively
        printTree(node.children.get(0), depth + 1, columnSize);

        // Print all children current node recursively
        for (int i = 1; i < node.children.size(); i++) {
            printLeading(depth + 1, columnSize);
            printTree(node.children.get(i), depth + 1, columnSize);
        }
    }
}

public void printLeading(int depth, int columnSize) {
    // Print the leading white spaces of column at a certain depth
    // Each node (depth) takes the column size + 2 characters (= "| ")
    for (int i = 0; i < depth * columnSize + depth * 2; i++) {
        System.out.print(" ");
    }
}

public void printNode(Node<String> node, int columnSize) {
    int trailing = columnSize - node.getData().length();
    System.out.print("| " + node.data);

    // Print the leading white spaces in the column
    for (int i = 0; i < trailing; i++) {
        System.out.print(" ");
    }
}

Answer 3

Probably you can achieve that using a simple DFS exploration of the tree. You keep track of the current depth of the tree, then at each node you print depth times a white column, followed by a column with the node's value.

public void printTree(TreeNode<T> node, int depth) {
    // Print leaf
    if(node.children.size() == 0) {
      System.out.print(node.data);
      System.out.print("\n");
      return;
    } else {

      // Print current node
      System.out.print(node.data);

      // Print next nodes at this level
      printTree(node.children.get(0), depth + 1);

      // Print remaining nodes with leading white columns
      for (int i = 1; i < node.children.size(); i++) {
        for (int j = 0; j < depth; j++) {
          System.out.print("   |");
        }
        System.out.print(node.children.get(i);
        System.out.print("\n");
      }
    }
}