title: Converting flat structure to typical parent-child tree in Java
body: <p>For some reason I'm drawing a blank on this, maybe my brain is overloaded lately but I can't seem to get it right. I'm trying to convert a structured list of unique values into a tree structure.</p>
  
  <p>I have a list of unique values that are set up in <a href="https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/keyvalue/MultiKey.html" rel="nofollow">Apache MultiKey</a> classes, which is basically just a wrapper for any number of objects that make up a key. They list looks like this:</p>
  
  <pre><code>List&lt;MultiKey&gt; _data = new ArrayList&lt;MultiKey&gt;()
  </code></pre>
  
  <p>And the data inside looks like this:</p>
  
  <pre><code>MultiKey[ABC]
  MultiKey[ABC, 111]
  MultiKey[ABC, 111, CHF]
  MultiKey[ABC, 111, CHF, AT000B049432]
  MultiKey[ABC, 111, CHF, CH0012814965]
  MultiKey[ABC, 111, CHF, CH0018550399]
  MultiKey[ABC, 111, CHF, CH0020626773]
  MultiKey[ABC, 111, EUR]
  MultiKey[ABC, 111, EUR, AT0000A001X2]
  MultiKey[ABC, 111, EUR, AT0000A0U3T4]
  MultiKey[ABC, 111, USD]
  MultiKey[ABC, 111, USD, CH0002497458]
  MultiKey[DEF]
  MultiKey[DEF, 222]
  MultiKey[DEF, 222, CHF]
  MultiKey[DEF, 222, CHF, AT000B049432]
  MultiKey[DEF, 222, CHF, CH0012814965]
  MultiKey[DEF, 222, EUR]
  MultiKey[DEF, 222, EUR, AT0000A001X2]
  </code></pre>
  
  <p>The class that makes up the Tree Node is a classic parent-child tree node that looks like this (additional methods excluded for simplicity).</p>
  
  <pre><code>public class DataTreeNode {
  
      private Object              _data;
      private DataTreeNode        _parent;
      private List&lt;DataTreeNode&gt;  _children;
  
      public DataTreeNode() {
          super();
      }
  
      public DataTreeNode(Object data) {
          super();
          _data = data;
      }
  
      public DataTreeNode getParent() {
          return _parent;
      }
  
      public void setParent(DataTreeNode parent) {
          _parent = parent;
      }
  
      public Object getData() {
          return _data;
      }
  
      public void addChild(DataTreeNode child) {
          if (!_children.contains(child)) {
              _children.add(child);
              child.setParent(this);
          }
      }
  
      public List&lt;DataTreeNode&gt; getChildren() {
          return _children;
      }
  
  }
  </code></pre>
  
  <p>The idea is to loop through the keys and (using sample data) to build a tree like this:</p>
  
  <pre><code>ABC
    111
      CHF
        AT000B049432
        CH0012814965
        CH0018550399
        CH0020626773
      EUR
        AT0000A001X2
        AT0000A0U3T4
      USD
        CH0002497458
  DEF
    222
      CHF
        AT000B049432
        CH0012814965
      EUR
        AT0000A001X2
  </code></pre>
  
  <p>Here's a fully runnable Java sample that builds the sample data using the MultiKey structure, but is missing the convert-to-tree implementation.</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.List;
  
  import org.apache.commons.collections.keyvalue.MultiKey;
  
  public class Sample {
  
      public static void main(String [] args) { 
          List&lt;MultiKey&gt; data = new ArrayList&lt;MultiKey&gt;();
  
          data.add(new MultiKey(new Object [] { "ABC" }));
          data.add(new MultiKey(new Object [] { "ABC", "111" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "CHF" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "AT000B049432" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0012814965" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0018550399" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "CHF", "CH0020626773" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "EUR" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "EUR", "AT0000A001X2" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "EUR", "AT0000A0U3T4" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "USD" }));
          data.add(new MultiKey(new Object [] { "ABC", "111", "USD", "AT0000A0U3T4" }));
          data.add(new MultiKey(new Object [] { "DEF" }));
          data.add(new MultiKey(new Object [] { "DEF", "222" }));
          data.add(new MultiKey(new Object [] { "DEF", "222", "CHF" }));
          data.add(new MultiKey(new Object [] { "DEF", "222", "CHF", "AT000B049432" }));
          data.add(new MultiKey(new Object [] { "DEF", "222", "CHF", "CH0012814965" }));
          data.add(new MultiKey(new Object [] { "DEF", "222", "EUR" }));
          data.add(new MultiKey(new Object [] { "DEF", "222", "EUR", "AT0000A001X2" }));
  
          DataTreeNode treeFromData = Sample.getTreeFor(data);
          // ...
      }
  
      public static DataTreeNode getTreeFor(List&lt;MultiKey&gt; data) {
          // TODO: THIS!
          return null;
      }
  }
  </code></pre>
  
  <p>Thanks in advance for any help solving this!</p>