Equivalent Binary Trees Exercise, achieving the "concurrency"

Question

I'm solving the exercise from A Tour of Go, Equivalent Binary Tree. This exercise requires one to implement a Walk function which is supposed to walk a tree and send all values orderly from the tree to a channel.

The exercise statement states:

... We'll use Go's concurrency and channels to write a simple solution.

Reading that line, I think it is challenging to implement the Walk in a way that it launches a goroutine for each left/right subtree and enabling the Walk to run faster (regarding time complexity) than non-concurrent version. Let me explain in more detail with codes.

This is my early code for Walk:

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    for v := range lch { ch <- v }

    ch <- t.Value

    go Walk(t.Right, rch)
    for v := range rch { ch <- v }

    return
}

It surely uses goroutines, but effectively isn't different from just traversing without goroutines because the ealry for v := range lch { ... } delays go Walk(t.Right, rch) until it ends.

It does not make any difference to move up go Walk(t.Right, rch):

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t == nil { return }
    
    lch, rch := make(chan int), make(chan int)
    go Walk(t.Left, lch)
    go Walk(t.Right, rch)

    for v := range lch { ch <- v }
    ch <- t.Value
    for v := range rch { ch <- v }
}

go Walk(t.Left, lch) walks along the entire left subtree (rooted on the blue) and values sent from lch are received immediately.

go Walk(t.Right, rch) tries to walk along as well but gets blocked as ch <- t.Value on the left-most node (the red) of the right subtree does so and propagates the blocking. This state persists until for v := range rch { ch <- v } is reached.

My question : How to implement Walk in a way that goroutines (corresponding to left or right) avoid being blocked by ch <- t.Value as much as possible?

Answer 1

右子树中的值需要一个缓冲区（例如缓冲通道），因为它们必须持续存在，直到这些（<-lch和t.Value）之前的值被消耗为止。

\n

为大小未知的子树准备缓冲区有几个含义

\n

\n
• make(chan int, N)如果使用缓冲通道，则选择N至关重要。如果N对于子树来说碰巧太小，则子树的 goroutine 阻塞得太快。如果太大，就会不必要地浪费内存。
\n
• 使用自动调整缓冲区大小来实现自定义通道可能是一种解决方案，但它会带来额外的复杂性和开销。我不知道惩罚是否会抵消性能增益。这取决于自定义通道如何管理其内部缓冲区或如何管理这些缓冲区的池。
\n

\n

在我看来，对于这种“遍历一棵随机的、未知的树，并发性被挤出”的问题，没有简单且通用的解决方案。

\n