Generating hierarchy from flat data

Question

I need to generate a hierarchy from flat data. This question is not for homework or for an interview test, although I imagine it'd make a good example for either one. I've seen this and this and this, none of them exactly fit my situation.

My data is as follows. I have a list of objects. Each object has a breadcrumb and a text. Examples are below:

Object 1:
---------
breadcrumb: [Person, Manager, Hourly, New]
text: hello world

Object 2:
---------
breadcrumb: [Person, Manager, Salary]
text: hello world again

And I need to convert that to a hierarchy:

Person
  |--Manager
       |--Hourly
            |--New
                 |--hello world
       |--Salary
             |--hello world again

I'm doing this in Java but any language would work.

@zEro: I'm stuck at the concept of how to approach this. I've tried making an `Item` class that has `List children` and an `Item parent`. But the concept is where I'm stuck. — David, Mar 18 '16 at 13:23
@David: This looks like a reasonable approach. Could you please provide your code? — Oli, Mar 18 '16 at 13:26
@David Good. So as you mentioned in your question - you're looking for a hierarchy. A Tree like datastructure can be a good representation for what you are looking for. See if that works for you. — zEro, Mar 18 '16 at 13:29

Alex Salauyou · Accepted Answer · 2016-03-18T13:48:42.613

You need a Trie datastructure, where each Node holds children in List<Node>

Trie itself should contain one Node--root, that initially is empty;
When new sequence arrives, iterate over its items trying to find corresponding value among existing children at the current Node, moving forward if corresponding item is found. Such you find a longest prefix existing in trie, common to a given sequence;
If longest common prefix doesn't cover entire sequence, use remaining items to build a chain of nodes where each node have only one child (next item), and attach it as child to a node at which you stopped at step (2).

You see, this is not so easy. Implementation code would be long and not obvious. Unfortunately, JDK doesn't have standard trie implementations, but you can try to find some existing or write your own.

For more details, see https://en.wikipedia.org/wiki/Trie#Algorithms

Generating hierarchy from flat data

1 Answers1