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!

P. van der Laan · Accepted Answer · 2019-01-08 20:02:37Z

1

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(" ");
    }
}

edited Jan 8, 2019 at 20:02

answered Jan 8, 2019 at 19:55

P. van der Laan

2211 silver badge9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Spanner0jjm Over a year ago

Thanks for your answer, but I think you slightly misunterstood my question. I am not trying to print the data, I am trying to populate a nested array, the 'table' that I showed is just to illustrate the problem, so you needn't worry about the lengths of the Strings. I am going to try to modify your answer to what I need - clearly a Depth First Search, but the difficulty I forsee is knowing where to 'carry on from' when passing the nested List between methods, rather than just printing 'more space' directly from the method.

Matteo Ugolotti · Accepted Answer · 2019-01-08 18:51:42Z

0

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");
      }
    }
}

edited Jan 8, 2019 at 18:51

answered Jan 8, 2019 at 16:03

Matteo Ugolotti

3673 silver badges12 bronze badges

2 Comments

Spanner0jjm Over a year ago

I don't think this is correct. Depth is not necessarily synonymous with the amount of whitespace that should be printed. A simple example: 'Root -> Child 1 -> Grandchild 1', should be printed as 1 line: '["Root", "Child 1", "Grandchild 1"]', whereas your solution would produce (if it were stored as an array and not printed) the more typical hierarchial structure: '[["Root", "", ""],["", "Child 1", ""],["", "", "Grandchild 1"]]'

Matteo Ugolotti Over a year ago

I modified a bit my code sample but more or less the same principle should apply.

Spanner0jjm · Accepted Answer · 2019-01-09 08:43:18Z

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.

Collectives™ on Stack Overflow

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

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related