CODEWITHSUNDEEP
algorithmgodata-structurestree
Pascal Riesinger
Pascal Riesinger

Reputation: 53

Convert map to tree in Go

I have a very specific problem, I cannot figure out a solution for.

I have a map[string]Metric, which I want to convert into a tree for using in a frontend. The Metric interface looks has a Path() and a Name() Method, the name method returns the last part of a period-separated path (so a path of 'my.awesome.metric' will mean that this metric has the name 'metric') The tree should be sorted by the path and should contain IndexNodes. This struct looks like this:

type IndexNode struct {
    Name string
    Path string
    Children []*IndexNode
}

So a map like this:

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

Should lead to a tree like this: (sorry for the crude ascii art)

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

Note that I only ever have one root node (my in this case). The order inside of the tree does not matter to me.

I tried my best and cannot figure it out... After lots of googleing (which only showed me how to create binary search trees and the GoDS library), I resigned and decided to ask my very first question here 😊

Thanks for your help!

Upvotes: 0

Views: 2331

Answers (2)

Ravi R
Ravi R

Reputation: 1782

Here's a solution using a map, traversing it can help you populate the data structure. Can create the nodes where it says "Parent xxx Child xxx" in the tree navigation https://play.golang.org/p/sVqBCVgiBG

Upvotes: 0

Milo Christiansen
Milo Christiansen

Reputation: 3294

Change Children to map[string]*IndexNode and you are halfway there. If you don't mind it being a lot slower to look stuff up, you can use a slice, but this means you need to search the slice to find the child you want every time you traverse the tree. A map is faster and easier in this case.

Now you just need to write a recursive function that steps down the tree, making nodes as needed for each element in the path until it reaches the end.

Unfortunately I don't have ready access to an example, all my code in on my other computer :(

A quick and dirty example:

type Tree struct {
    Parent *Tree
    Children map[string]*Tree
    Payload bool // Your 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 it on the Go Playground!

Upvotes: 1

Related Questions