CODEWITHSUNDEEP
gotree
Jose Bagatelli
Jose Bagatelli

Reputation: 1409

Build a tree structure from parent/child pairs in GO

I'm trying to build a tree structure from parent x child dataset in Go. Ultimately the data will come from a MySQL table but to simplify this example I have removed the database out of the equation and created an array instead. The principle will be the same for the "real life" solution.

The data source looks like this:

---------------------------
    ID      |   Parent
---------------------------
    1       |       0
    2       |       1
    3       |       1
    4       |       0
    5       |       4
    6       |       4
    7       |       0
    8       |       7
    9       |       2

The Parent colunm refer back to the ID column forming the parent x child relationship. ID's with parent = 0 are root elements.

This is my attempt to solve this problem. It works for root elements and first level childs, however it doesn't go deeper than that in the tree. My understand is that I need a recursive loop to achieve what I want but I'm having trouble to work out the deeper levels.

https://play.golang.org/p/6m0YTqe529O

The expected output from the data source above is a hierarchical tree as such:

(Represented in JSON to facilitate visualisation).

[{
        "id": 1,
        "child": [{
                "id": 2,
                "child": [{
                    "id": 9
                }]
            },
            {
                "id": 3
            }
        ]
    },
    {
        "id": 4,
        "child": [{
            "id": 5
        }, {
            "id": 6
        }]
    },
    {
        "id": 7,
        "child": [{
            "id": 8
        }]
    }
]

I've seen similar questions on S.O. but the answers either don't go any higher than the first level or don't simply solve the problem altogether.

Upvotes: 0

Views: 3430

Answers (1)

Jimeux
Jimeux

Reputation: 3026

Firstly, you should never use pointers to slices unless you really have to. It's more typical to assign a return value to the variable, e.g. mySlice = sliceReturningFunction().

I'm not sure what all the requirements here are, but one solution could be:

  1. Build a map of parent-child relations (map[int][]int).
  2. Pass the root-level relation to a function that recursively builds the categories.

Here's an example recursive function. Note that it returns a new slice rather than mutating a pointer. 

func buildCategories(ids []int, relations map[int][]int) []Category {
    categories := make([]Category, len(ids))
    for i, id := range ids {
        c := Category{ID: id}
        if childIDs, ok := relations[id]; ok {
            c.Child = buildCategories(childIDs, relations)
        }
        categories[i] = c
    }
    return categories
}

I added a full example on the Playground. It's not tested, and I'm sure there are better solutions, but it's simple and might give you some ideas at least. If you're going to have thousands of nodes and this is accessed frequently, you're going to need to optimise beyond Go code alone though.

Upvotes: 6

Related Questions