CODEWITHSUNDEEP
javahierarchyhierarchical-datatriehierarchical
David
David

Reputation: 1494

Generating hierarchy from flat data

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.

Upvotes: 2

Views: 340

Answers (1)

Alex Salauyou
Alex Salauyou

Reputation: 14338

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

  1. Trie itself should contain one Node--root, that initially is empty;

  2. 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;

  3. 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

Upvotes: 3

Related Questions