print departments hierarchy to a table

Question

I have a relationship table for departments as below:

+---------------+----------------+
|     Dept.     | superior Dept. |
+---------------+----------------+
| "00-01"       | "00"           |
| "00-02"       | "00"           |
| "00-01-01"    | "00-01"        |
| "00-01-02"    | "00-01"        |
| "00-01-03"    | "00-01"        |
| "00-02-01"    | "00-02"        |
| "00-02-03"    | "00-02"        |
| "00-02-03-01" | "00-02-03"     |
+---------------+----------------+

Now I want to list them according to their tiers like this:

+-----------+--------------+--------------+--------------+
| Top Dept. | 2-tier Dept. | 3-tire Dept. | 4-tier Dept. |
+-----------+--------------+--------------+--------------+
|        00 |              |              |              |
|           | 00-01        |              |              |
|           |              | 00-01-01     |              |
|           |              | 00-01-02     |              |
|           | 00-02        |              |              |
|           |              | 00-02-01     |              |
|           |              | 00-02-03     |              |
|           |              |              | 00-02-03-01  |
+-----------+--------------+--------------+--------------+

I can construct the relationship tree using the code below:
TreeNode.java

import java.util.LinkedList;
import java.util.List;

public class TreeNode {
  public String value;
  public List children = new LinkedList();

  public TreeNode(String rootValue) {
    value = rootValue;
  }

}

PairsToTree.java

import java.util.*;

public class PairsToTree {

  public static void main(String[] args) throws Exception {
    // Create the child to parent hash map
    Map <String, String> childParentMap = new HashMap<String, String>(8);
    childParentMap.put("00-01", "00");
    childParentMap.put("00-02", "00");
    childParentMap.put("00-01-01", "00-01");
    childParentMap.put("00-01-02", "00-01");
    childParentMap.put("00-01-03", "00-01");
    childParentMap.put("00-02-01", "00-02");
    childParentMap.put("00-02-03", "00-02");
    childParentMap.put("00-02-03-01", "00-02-03");

    // All children in the tree
    Collection<String> children = childParentMap.keySet();

    // All parents in the tree
    Collection<String> values = childParentMap.values();

    // Using extra space here as any changes made to values will
    // directly affect the map
    Collection<String> clonedValues = new HashSet();
    for (String value : values) {
      clonedValues.add(value);
    }

    // Find parent which is not a child to any node. It is the
    // root node
    clonedValues.removeAll(children);

    // Some error handling
    if (clonedValues.size() != 1) {
      throw new Exception("More than one root found or no roots found");
    }

    String rootValue = clonedValues.iterator().next();
    TreeNode root = new TreeNode(rootValue);

    HashMap<String, TreeNode> valueNodeMap = new HashMap();
    // Put the root node into value map as it will not be present
    // in the list of children
    valueNodeMap.put(root.value, root);

    // Populate all children into valueNode map
    for (String child : children) {
      TreeNode valueNode = new TreeNode(child);
      valueNodeMap.put(child, valueNode);
    }

    // Now the map contains all nodes in the tree. Iterate through
    // all the children and
    // associate them with their parents
    for (String child : children) {
      TreeNode childNode = valueNodeMap.get(child);
      String parent = childParentMap.get(child);
      TreeNode parentNode = valueNodeMap.get(parent);
      parentNode.children.add(childNode);
    }

    // Traverse tree in level order to see the output. Pretty
    // printing the tree would be very
    // long to fit here.
    Queue q1 = new ArrayDeque();
    Queue q2 = new ArrayDeque();
    q1.add(root);
    Queue<TreeNode> toEmpty = null;
    Queue toFill = null;
    while (true) {
      if (false == q1.isEmpty()) {
        toEmpty = q1;
        toFill = q2;
      } else if (false == q2.isEmpty()) {
        toEmpty = q2;
        toFill = q1;
      } else {
        break;
      }
      while (false == toEmpty.isEmpty()) {
        TreeNode node = toEmpty.poll();
        System.out.print(node.value + ", ");
        toFill.addAll(node.children);
      }
      System.out.println("");
    }
  }

}

but can't figure it out how to format the output to resemble a table. Or is there a sql statement/stored procedure(like this question) to do this?

EDIT: the Dept. name is just a sample for the sake of convenience, it can be arbitrary string.

Answer 1

You have not noted what RDBMS you are using, but if it happens to be MS SQL Server or certain versions of Oracle(see edit below), and merely as a service for those of us that use T-SQL and are interested in this question, you can use a recursive CTE to accomplish this in SQL Server.

EDIT: Oracle (with which I have very, very little experience) appears to support recursion as well, including recursive CTE's since 11g Release 2. See this question for more information.

Given this setup:

CREATE TABLE hierarchy
    ([Dept] varchar(13), [superiorDept] varchar(12))
;

INSERT INTO hierarchy
    ([Dept], [superiorDept])
VALUES
    ('00',NULL),
    ('00-01', '00'),
    ('00-02', '00'),
    ('00-01-01', '00-01'),
    ('00-01-02', '00-01'),
    ('00-01-03', '00-01'),
    ('00-02-01', '00-02'),
    ('00-02-03', '00-02'),
    ('00-02-03-01', '00-02-03')
;

This recursive CTE:

WITH cte AS (
SELECT 
  Dept,
  superiorDept,
  0 AS depth,
  CAST(Dept AS NVARCHAR(MAX)) AS sort
FROM hierarchy h
WHERE superiorDept IS NULL

UNION ALL

SELECT 
  h2.Dept,
  h2.superiorDept,
  cte.depth + 1 AS depth,
  CAST(cte.sort + h2.Dept AS NVARCHAR(MAX)) AS sort
FROM hierarchy h2
INNER JOIN cte ON h2.superiorDept = cte.Dept
)

SELECT 
  CASE WHEN depth = 0 THEN Dept END AS TopTier,
  CASE WHEN depth = 1 THEN Dept END AS Tier2,
  CASE WHEN depth = 2 THEN Dept END AS Tier3,
  CASE WHEN depth = 3 THEN Dept END AS Tier4
FROM cte
ORDER BY sort

Will render the desired output:

 TopTier    Tier2   Tier3     Tier4
 00 
            00-01   
                    00-01-01
                    00-01-02
                    00-01-03
            00-02
                    00-02-01
                    00-02-03
                              00-02-03-01

Here is a SQLFiddle to demonstrate

This should work regardless of the contents or type of the two columns involved in the adjacency list. As long as parent values match id values, the CTE should have no problem generating depth and sort information.

The only caveat for doing this entirely in SQL is that you have to define a set number of columns manually, but this is nearly always the case when dealing with SQL. You may wish to generate the CTE, then pass the already sorted results to your program and use the depth information to make column manipulation trivial.

Answer 2

here is a test case based on your data that prints the departments in a tabular way, try to run it and see what happens

package test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class DeptHierachy {
    public Map<String,List<String>> deptMap= new HashMap<>();
    public static void main(String[] args) {
        TreeNode tn=new TreeNode("00");
        tn.addChildTo("00-01", "00");
        tn.addChildTo("00-02", "00");
        tn.addChildTo("00-01-01", "00-01");
        tn.addChildTo("00-01-02", "00-01");
        tn.addChildTo("00-01-03", "00-01");
        tn.addChildTo("00-02-01", "00-02");
        tn.addChildTo("00-02-03", "00-02");
        tn.addChildTo("00-02-03-01", "00-02-03");
        tn.print();
        //System.out.println("max height=" + tn.maxHeigth());
    }



    public static class TreeNode {
          public String value;
          public List<TreeNode> children = new LinkedList<>();

          public TreeNode(String rootValue) {
            value = rootValue;
          }

          public boolean addChildTo(String childName, String parentName) {
              if (parentName.equals(value)) {
                  for (TreeNode child:children) {
                      if (child.getValue().equals(childName)) {
                          throw new IllegalArgumentException(parentName + " already has a child named " + childName);
                      }
                  }
                  children.add(new TreeNode(childName));
                  return true;
              } else {
                  for (TreeNode child:children) {
                      if (child.addChildTo(childName, parentName)) {
                          return true;
                      }
                  }
              }
              return false;
          }

        public String getValue() {
            return value;
        }

        public void print() {
            int maxHeight=maxHeigth();
            System.out.printf("|%-20.20s",value);

            for (int i=0;i<maxHeight-1;i++) {
                System.out.printf("|%-20.20s","");
            }
            System.out.println("|");
            for (TreeNode child:children) {
                child.print(1,maxHeight);
            }
        }

        public void print(int level, int maxHeight) {
            for (int i=0;i<level;i++) {
                System.out.printf("|%-20.20s","");
            }
            System.out.printf("|%-20.20s",value);
            for (int i=level;i<maxHeight-1;i++) {
                System.out.printf("|%-20.20s","");
            }
            System.out.println("|");
            for (TreeNode child:children) {
                child.print(level+1,maxHeight);
            }
        }

        public int maxHeigth() {
            int localMaxHeight=0;
            for (TreeNode child:children) {
                int childHeight = child.maxHeigth();
                if (localMaxHeight < childHeight) {
                    localMaxHeight = childHeight;
                }
            }
            return localMaxHeight+1;
        }
    }   

}

Answer 3

Go through the values counting - chars. The max - char count +1 is the table column count. Values size is row count.

You can define a matrix e.g. String[][] for the table.

For each value you can find column (calculating - chars in the String value). Now to find row you should check previous column to find parent String.

If it's found just insert a new row after the found parent's row shifting down all the rest rows.

If parent String is not found insert the parent first (based on the childParentMap).

If parent is null just insert a new row to the end.

Answer 4

import java.util.LinkedList;
import java.util.List;

public class TreeNode {
  private String value;
  private int depth;
  private List children = new LinkedList<TreeNode>();

  public TreeNode(String rootValue, int depth) {
      value = rootValue;
      this.depth = depth;
  }


  public boolean add(String parent, String child) {
      if (this.value.equals(parent)) {
          this.children.add(new TreeNode(child, depth + 1));
          return true;
      } else {
          for (TreeNode node : children) {
              if (node.add(parent, child)) {
                  return true;
              }
          }
      }
      return false;
  }

  public String print() {
      StringBuilder sb = new StringBuilder();
      sb.append(format());
      for (TreeNode child : children) {
          sb.append(child.print())
      }
      return sb.toString();
  }

  public String format() {
      // Format this node according to depth;
  }

}

First print the Top Dept., then call print() on Top Dept.