Recursive data structures

I try to figure out how to make a tree from a flat structure.
I have this:
package main
import “fmt”

//DataFlat node
type DataFlat struct {
IDGeoRegion int
IDParent int
Description string
}

func main() {

dFlatlist := []DataFlat{}

dFlat := DataFlat{IDGeoRegion: 1, IDParent: 0, Description: "Organisation"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 2, IDParent: 1, Description: "Office"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 3, IDParent: 2, Description: "Office Zürich"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 4, IDParent: 2, Description: "Office Brazil"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 5, IDParent: 1, Description: "Storage"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 6, IDParent: 5, Description: "Storge Zürich"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 7, IDParent: 5, Description: "Storge Brazil"}
dFlatlist = append(dFlatlist, dFlat)

fmt.Println(dFlatlist)
//Result: [{1 0 Organisation} {2 1 Office} {3 2 Office Zürich} {4 2 Office Brazil} {5 1 Storage} {6 5 Storge Zürich} {7 5 Storge Brazil}]

}

Now i need a recursive function that processes dFlatList and builds it as a tree structure with this format:

type GeoTree struct {
IDGeoRegion int
IDParent int
Description string
Children []*GeoTree
}

Any help or advise would be greatly appreciated

Thanks
Theo

1 Like

I have tried creating a tree with map based approach. If I get it right IDParent will be IDGeoRegion for children node.

func (g GeoTree) print() {

	var list []GeoTree

	list = append(list, g)

	i := 0
	for {
		element := list[i]
		fmt.Println(element)
		for _, value := range element.Children {
			list = append(list, *value)
		}
		i++
		if i == len(list) {
			break
		}
	}

}

func addNode(d DataFlat) (g GeoTree) {
	g.IDGeoRegion = d.IDGeoRegion
	g.IDParent = d.IDParent
	g.Description = d.Description
	return
}

inside main function add this

root := addNode(dFlatlist[0])

m := map[int]*GeoTree{}

m[root.IDGeoRegion] = &root

for i := 1; i < len(dFlatlist); i++ {

	if m[dFlatlist[i].IDParent] == nil {
		fmt.Println("parent does not exist", dFlatlist[i].IDGeoRegion) //instead of printing we can create a queue and store these flat into it and after this loop ,reiterate through this queue and add then again.
	} else {
		node := addNode(dFlatlist[i])
		m[dFlatlist[i].IDParent].Children = append(m[dFlatlist[i].IDParent].Children, &node)
		m[dFlatlist[i].IDGeoRegion] = &node
	}
}

root.print()
1 Like

Hello Shubh,

your solution works perfect, exactly what i was looking for.

Thank you very much!

2 Likes

At first it looked like this works for me, but i run into a problem. The above solution seems to require that the flat data list is in the right order, but in my case i can not be sure about that.

If i build the flatlist out of order like, ‘Storage Zürich and Storage Brazil’ inserted before ‘Storage’ in that case the solution does not work.

Is there a way to still do this when the only thing guarantied is that the first entry in the list is the root element, but after that entries are not sorted ?

This is the code that does not work because of the dFlatlist order:

package main

import “fmt”

//DataFlat node
type DataFlat struct {
IDGeoRegion int json:"idgeoregion" db:"IdGeoRegion"
IDParent int json:"idparent" db:"IdParent"
Description string json:"description" db:"Description"
}

//GeoTree tree
type GeoTree struct {
IDGeoRegion int json:"idgeoregion" db:"IdGeoRegion"
IDParent int json:"idparent" db:"IdParent"
Description string json:"description" db:"Description"
Children []*GeoTree
}

func main() {

dFlatlist := []DataFlat{}

dFlat := DataFlat{IDGeoRegion: 1, IDParent: 0, Description: "Organisation"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 6, IDParent: 5, Description: "Storge Zürich"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 7, IDParent: 5, Description: "Storge Brazil"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 2, IDParent: 1, Description: "Office"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 3, IDParent: 2, Description: "Office Zürich"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 4, IDParent: 2, Description: "Office Brazil"}
dFlatlist = append(dFlatlist, dFlat)

dFlat = DataFlat{IDGeoRegion: 5, IDParent: 1, Description: "Storage"}
dFlatlist = append(dFlatlist, dFlat)

//fmt.Println(dFlatlist)
//Result: [{1 0 Organisation} {2 1 Office} {3 2 Office Zürich} {4 2 Office Brazil} {5 1 Storage} {6 5 Storge Zürich} {7 5 Storge Brazil}]
root := addNode(dFlatlist[0])

m := map[int]*GeoTree{}

m[root.IDGeoRegion] = &root

for i := 1; i < len(dFlatlist); i++ {

	if m[dFlatlist[i].IDParent] == nil {
		fmt.Println("parent does not exist", dFlatlist[i].IDGeoRegion)
	} else {
		node := addNode(dFlatlist[i])
		m[dFlatlist[i].IDParent].Children = append(m[dFlatlist[i].IDParent].Children, &node)
		m[dFlatlist[i].IDGeoRegion] = &node
	}
}

root.print()

}

func (g GeoTree) print() {
var list []GeoTree
list = append(list, g)
i := 0
for {
element := list[i]
fmt.Println(element)
for _, value := range element.Children {
list = append(list, *value)
}
i++
if i == len(list) {
break
}
}
}
func addNode(d DataFlat) (g GeoTree) {
g.IDGeoRegion = d.IDGeoRegion
g.IDParent = d.IDParent
g.Description = d.Description
return
}

2 Likes

i have added a comment on if condition . You can create a queue and store those flat whose parent is not present in map and after for loop iterate through the queue and again do the same thing.

2 Likes

Build the GeoTree in two steps. In the first step, you scan the dataFlat and instantiate all GeoTree elements by storing them in a map with their ID as key. During this step, you ignore the parentID. In a second step, you rescan dataFlat, locate the corresponding GeoTree element In the map, and add it as child of the corresponding parent.

3 Likes

I did what Shubh suggested, created a queue for those whose parent is not present in map, and then loop over this queue.

This works and i can use it this way, again, thanks a lot for your help!

I like Christoph’s input, that sounds like a good way to do it, i have to work on that and see if i can figure it out on my own.

3 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.