Golang: Create nested from linear array bassed on id and parent id

Issue

I have a data linear of name such as:

  • name: One, Id: 1, ParentId: 0
  • name: One-One, Id: 2, ParentId: 1
  • name: One-One-One, Id: 3, ParentId: 2
  • name: One-One-Two, Id: 4, ParentId: 2

For example this data, I get from the database, but I think to test the logic I make the dummy data to struct.
I think I make a temporary index, for data recursively. I set if data does not exist in a map, and I get index if data has to append for before slice. But, I think in function recursive (i show it bellow), it doesn’t work (data not append). Why?
is there any wrong algorithm logic?

And what is the right solution for my result is

[
  {
    "id": 1,
    "name": "One",
    "children": [
      {
        "id": 2,
        "name": "One-One",
        "children": [
          {
            "id": 3,
            "name": "One-One-One",
            "children": null
          },
          {
            "id": 4,
            "name": "One-One-Two",
            "children": null
          }
        ]
      }
    ]
  }
]

Full code in golang:

package main

import (
    "encoding/json"
    "fmt"
)

type Data struct {
    Id       int    `json:"id"`
    ParentId int    `json:"parent_id"`
    Name     string `json:"name"`
}

type Datas []Data

type Response struct {
    Id       int       `json:"id"`
    Name     string    `json:"name"`
    Children Responses `json:"children"`
}

type Responses []*Response

func main() {
    datas := Datas{
        {
            Name: "One",
            Id:   1,
        },
        {
            Name:     "One-One",
            Id:       2,
            ParentId: 1,
        },
        {
            Name:     "One-One-One",
            Id:       3,
            ParentId: 2,
        },
        {
            Name:     "One-One-Two",
            Id:       4,
            ParentId: 2,
        },
    }

    var result Responses
    tempIdx := make(map[int]int)

    for _, val := range datas {
        res := Response{
            Id:   val.Id,
            Name: val.Name,
        }

        if val.ParentId == 0 {
            result = append(result, &res)
            tempIdx[val.Id] = len(result) - 1
            continue
        } else {
            recursive(val.ParentId, result, res, tempIdx)
        }

    }

    json, err := json.Marshal(result)
    if err != nil {
        panic(err)
    }
    fmt.Println(string(json))
}

func recursive(idxParent int, datas Responses, res Response, tempIdx map[int]int) {
    idxData, ok := tempIdx[idxParent]
    if ok {
        // don't work in this "datas[idxData].Children", why?
        recursive(idxData, datas[idxData].Children, res, tempIdx)
    } else {
        datas = append(datas, &res)
        tempIdx[res.Id] = len(datas) - 1
    }
}

Open with Golang Playground

Solution

Slice is not an array

appending to slice in function doesn’t increase length and capacity of original slice.

change := func(slice []int) {
    slice = append(slice, 3)
}
slice := []int{1, 2}
change(slice)
fmt.Println(slice) 
// Output: [1 2]

Anyway even if you fix the slice issue your output won’t be as expected. You are basically using a Tree data structure so it’s recommended to use some of tree searching algorithms. Here’s your working example with BFS

package main

import (
    "encoding/json"
    "fmt"
)

type Data struct {
    Id       int    `json:"id"`
    ParentId int    `json:"parent_id"`
    Name     string `json:"name"`
}

type Datas []Data

type Response struct {
    Id       int       `json:"id"`
    Name     string    `json:"name"`
    Children Responses `json:"children"`
}

type Responses []*Response

func main() {
    datas := Datas{
        {
            Name: "One",
            Id:   1,
        },
        {
            Name:     "One-One",
            Id:       2,
            ParentId: 1,
        },
        {
            Name:     "One-One-One",
            Id:       3,
            ParentId: 2,
        },
        {
            Name:     "One-One-Two",
            Id:       4,
            ParentId: 2,
        },
    }

    var result Responses
    for _, val := range datas {
        res := &Response{
            Id:   val.Id,
            Name: val.Name,
        }

        var found bool

        // iterate trough root nodes
        for _, root := range result {
            parent := findById(root, val.ParentId)
            if parent != nil {
                parent.Children = append(parent.Children, res)

                found = true
                break
            }
        }

        if !found {
            result = append(result, res)
        }
    }

    out, err := json.Marshal(result)
    if err != nil {
        panic(err)
    }
    fmt.Println(string(out))
}

func findById(root *Response, id int) *Response {
    queue := make([]*Response, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        nextUp := queue[0]
        queue = queue[1:]
        if nextUp.Id == id {
            return nextUp
        }
        if len(nextUp.Children) > 0 {
            for _, child := range nextUp.Children {
                queue = append(queue, child)
            }
        }
    }
    return nil
}

Answered By – medasx

Answer Checked By – Gilberto Lyons (GoLangFix Admin)

Leave a Reply

Your email address will not be published.