title: Generating Hierarchy using Maps and path variable
body: <p>I've got a family class that pulls data from a postgres database. The class looks like something like this:</p>
  
  <pre><code>@Entity
  public class Family(){
  @Id
  private long id;
  private String firstName;
  private String lastName;
  private Long parentId;
  private4 String familyPath;
  private List&lt;Family&gt; children;
  
  //getters and setters
  </code></pre>
  
  <p>In the database, I have their relation to each other stored as a period-delimited string. So for example, if Bob is the child of Sue, the tree column would look like: "bob.sue". This path is stored as part of the family object in the familyPath variable.</p>
  
  <p><strong>CLARIFICATION</strong>
  familyPath is a path based on unique IDs for each row in the database. So a path may look like "1.2.3" where the last number is the current row. 
  "1.2.4" is another potential path. so rows with IDs 3 and 4 are children of 2, etc.</p>
  
  <p>In my code I query the database for all family members in the data, so I have a set of every member of the family in the database. My goal is to generate a set of all family members as a hierarchical structure using this initial, flat set. So, in the end if I call getChildren on Bob, I get a list back containing Sue and any other children.</p>
  
  <p><strong>My Solution:</strong></p>
  
  <p>First, I iterate through my list of families, and find what I call the root members -- those at the top level of the family path -- and remove them into a separate list. So now I have a list of top level family members, an a list of everyone else. </p>
  
  <p>Then, for each member in the top level list, I call the following recursive method:</p>
  
  <pre><code>private Family familyTree(Family root, List&lt;Family&gt; members) {
      List&lt;Family&gt; children = new ArrayList&lt;&gt;();
  
  
      for (Family f : members) {
          if (isChildOf(f, root)) {
              children.add(familyTree(f, resources));
          }
      }
      root.setChildren(children);
      return root;
  }
  
  
  private boolean isChildOf(Family a, Family b) {
      String pCPath = a.getFamilyPath();
      String pPPath = b.getFamilyPath();
  
      return pCPath.indexOf('.') &gt;= 0
              &amp;&amp; pCPath.substring(0, pCPath.lastIndexOf('.')).equals(pPPath);
  }
  </code></pre>
  
  <p>and save the output to a list. This generates the desired results.</p>
  
  <p><strong>My Question</strong>
  However, I feel that this recursive method is very expensive (n^2). I'm thinking that there may be a more efficient way to generate this hierarchy using sets, maps and the Family object's familyPath variable, But i keep getting stuck in multiple iterative loops. Does anyone have any thoughts? </p>