algorithm - Convert map to tree in Go -

i have specific problem, cannot figure out solution for.

i have map[string]metric, want convert tree using in frontend. metric interface looks has path() , name() method, name method returns last part of period-separated path (so path of 'my.awesome.metric' mean metric has name 'metric') tree should sorted path , should contain indexnodes. struct looks this:

type indexnode struct {     name string     path string     children []*indexnode } 

so map this:

{     my.awesome.metric.downloads     my.awesome.othermetric.downloads     my.awesome.othermetric.uploads     my.other.cool.metric } 

should lead tree this: (sorry crude ascii art)

     +-- other -- cool -- metric      | --+             +-- metric -- downloads      |             |      +-- awesome --+                 +-- downloads                    |                 |                    +-- othermetric --+                                      |                                      +-- uploads 

note ever have 1 root node (my in case). order inside of tree not matter me.

i tried best , cannot figure out... after lots of googleing (which showed me how create binary search trees , gods library), resigned , decided ask first question here 😊

thanks help!

change children map[string]*indexnode , halfway there. if don't mind being lot slower stuff up, can use slice, means need search slice find child want every time traverse tree. map faster , easier in case.

now need write recursive function steps down tree, making nodes needed each element in path until reaches end.

unfortunately don't have ready access example, code in on other computer :(

a quick , dirty example:

type tree struct {     parent *tree     children map[string]*tree     payload bool // data here }  func newtree(parent *tree, path []string, payload bool) *tree {     if parent == nil {         parent = &tree{nil, map[string]*tree{}, false}     }     if len(path) == 0 {         parent.payload = payload         return parent     }      child := parent.children[path[0]]     if child == nil {         child = &tree{parent, map[string]*tree{}, false}         parent.children[path[0]] = child     }     return newtree(child, path[1:], payload) } 

usage:

root := newtree(nil, nil, false) newnode := newtree(root, []string{"a", "b", "c"}, true) 

try on go playground!