Utilizing goroutines and channels for top-to-bottom tree building function

Question

I'm new with golang and channels/goroutines, but I understand the concept and simple usage.

Now I'm trying to implement concurrent tree building function, the algorithm is pretty simple - from top to bottom for each node I add 2 children and then for each child I do the same operation depthLimit times. Here is the code for non-concurent one:

package main

import (
    "encoding/json"
    "fmt"
    "time"
)

type Node struct {
    Name     string
    Children []Node
}

func main() {
    mainNode := Node{"p", nil}
    AddChildrenToNode(&mainNode, 4, 0)

    b, _ := json.MarshalIndent(mainNode, "", "  ")
    fmt.Println(string(b)) // print as json
}

func AddChildrenToNode(node *Node, depthLimit int, curDepth int) {
    curDepth++
    if curDepth >= depthLimit {
        return // reached depth limit
    }

    time.Sleep(500 * time.Millisecond) // imitating hard work c:
    fmt.Print(".")                     // status indicator
    // add children
    node.Children = []Node{
        Node{node.Name + "-l", nil},
        Node{node.Name + "-r", nil},
    }
    for idx, _ := range node.Children {
        AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
    }
}

But now I face difficulties rewriting it for goroutine usage. The problem is we can't actually know when 'building' is finished and signal to block/unblock main. Am I missing something? I also tried to play with sync.WaitingGroup.

Answer 1

One way you can introduce goroutines into this algorithm is to use a separate goroutine for the addition of child nodes, assuming you can't really add those before you finish the "hard work" section.

func AddChildrenToNode(node *Node, wg *sync.WaitGroup,depthLimit int, curDepth int) {
  // work
  go func() {
    defer wg.Done()
    node.Children = []Node{
        Node{node.Name + "-l", nil},
        Node{node.Name + "-r", nil},
    }
    for idx, _ := range node.Children {
        AddChildrenToNode(&node.Children[idx], depthLimit, curDepth) // run this for every created child, recursively
    }
  }()
}

With this scheme, you end up creating 2^(depth-1)-1 goroutines, so you can wait in main for them to complete:

func main() {
 ...
  wg:=sync.WaitGroup{}
  wg.Add((1<<(depth-1))-1)
  AddChildrenToNode(&mainNode, 4, 0)
  wg.Wait()
  ...

There are other ways this can be done, like adding a goroutine for left-right nodes.