How to generate a tree (parent-child) in json format from a map

user_6603144 0
Viewed 386

What do I want?

To get a tree in JSON format from a Map.

Data to be used:

A map (key-value pairs), having keys as parents and their respective values as children

Code: The following code uses sample data, I want to use big data later on means having more parents-children. How can I structure parent-child from a Map? Please let me know if I need any other information to parse Map data into a tree structure?

type Nodes struct  {
      fn string
      children []*Nodes
}

func main() {
    var m map[string][]string
    m = make(map[string][]string)
    //map of parents(key) and child(values)
    m["root_node"] = []string{"1","2","3","4"}
    m["1"] = []string{"5","6"}
    m["2"] = []string{"7"}
    m["3"] = []string{"8", "9"}
    m["5"] = []string{"10"}
    m["7"] = []string{"11"}
    m["8"] = []string{"12","13"}

//json format: I don't know how to get root_node so expected result can be achieved
bytes, err := json.Marshal(root_node)
if err != nil {
    log.Fatal(err)
}
}

My expectation:

{
   "Funcname": "root_node",
   "Nodes": [
      {
         "Funcname": "1",
         "Nodes": [
            {
               "Funcname": "5",
               "Nodes": [
                  {
                     "Funcname": "10",
                     "Nodes": null
                  }
               ]
            },
            {
               "Funcname": "6",
               "Nodes": null
            }
         ]
      },
      {
         "Funcname": "2",
         "Nodes": [
            {
               "Funcname": "7",
               "Nodes": [
                  {
                     "Funcname": "11",
                     "Nodes": null
                  }
               ]
            }
         ]
      },
      {
         "Funcname": "3",
         "Nodes": [
            {
               "Funcname": "8",
               "Nodes": [
                  {
                     "Funcname": "12",
                     "Nodes": null
                  },
                  {
                     "Funcname": "13",
                     "Nodes": null
                  }
               ]
            },
            {
               "Funcname": "9",
               "Nodes": null
            }
         ]
      },
      {
         "Funcname": "4",
         "Nodes": null
      }
   ]
}
go tree data-structures
2 Answers

easier approach

We can also say that it is cleaner approach, to construct nodes with constructor syntax.

type Node struct {
    Name     string
    Children []*Node
}

func first_example() {
    root := Node{
        Name: "1",
        Children: []*Node{
            {
                Name: "3",
                Children: []*Node{
                    {
                        Name: "5",
                    },
                },
            },
        },
    }

    bytes, err := json.Marshal(root)
    if err != nil {
        panic(err)
    }

    fmt.Println(string(bytes))
}

harder approach

The output is the same but its lot more dynamic and allows you to store additional values, On the other hand traversing the tree is lot more annoying as you have to always cast everything.

func second_example() {
    root := map[string]interface{}{
        "Name": "1",
        "Children": []map[string]interface{}{
            {
                "Name": "3",
                "Children": []map[string]interface{}{
                    {
                        "Name": "5",
                    },
                },
            },
        },
    }

    bytes, err := json.Marshal(root)
    if err != nil {
        panic(err)
    }

    fmt.Println(string(bytes))
}

output

{"Name":"1","Children":[{"Name":"3","Children":[{"Name":"5","Children":null}]}]} // #1
{"Children":[{"Children":[{"Name":"5"}],"Name":"3"}],"Name":"1"} // #2

edit

In addition here is the function to insert a node to the structure. False is returned if operation fails.

func (n *Node) InsertNode(path string, o *Node) bool {
    parts := strings.Split(path, " ")
    target := n
    for _, part := range parts {
        found := false
        for _, child := range target.Children {
            if child.Name == part {
                target = child
                found = true
                break
            }
        }
        if !found {
            return false
        }
    }

    target.Children = append(target.Children, o)
    return true
}

func third_example() {
    root := &Node{Name: "1"}
    root.Children = append(root.Children, &Node{Name: "3"})
    root.InsertNode("3", &Node{Name: "5"})

    bytes, err := json.Marshal(root)
    if err != nil {
        panic(err)
    }

    fmt.Println(string(bytes))
}
user_139953110

First define a Node type with AddChild() method -

type Node struct {
    Fn       string  `json:"Funcname"`
    Children []*Node `json:"Nodes"`
}

func (node *Node) AddChild(child *Node) {
    node.Children = append(node.Children, child)
}

A constructor function to construct a new node for given fn -

func CreateNewNode(fn string) *Node {
    newNode := new(Node)
    newNode.Fn = fn
    return newNode
}

To generate a tree from map define MakeTreeFromMap()function as follows -

// MakeTreeFromMap generates a tree from given map and returns pointer to root node of tree.
func MakeTreeFromMap(treeMap map[string][]string, rootNodeFn string) *Node {
    cache := make(map[string]*Node)
    for fn, children := range treeMap {
        if _, nodeExists := cache[fn]; !nodeExists {
            node := CreateNewNode(fn)
            cache[fn] = node
        }
        for _, childFn := range children {
            if _, childExists := cache[childFn]; !childExists {
                child := CreateNewNode(childFn)
                cache[childFn] = child
            }
            cache[fn].AddChild(cache[childFn])
        }
    }
    return cache[rootNodeFn]
}

Serialize tree into JSON -

root_node := MakeTreeFromMap(m, "root_node")
bytes, err := json.Marshal(root_node)
if err != nil {
    log.Fatal(err)
}

See Go Playground for full working example.

user_72811430
Related