Compare Two trees are equivalent in Golang Using goroutines

Question

Without using channels i am able to compare the two trees are Equivalent or not but with using the channels i am not able to figure it out how to do.

Here is my sample code written using channels.

func Walk(t *Tree, ch chan int) {
    if t == nil {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}

func Same(t1, t2 *Tree) bool {

    t1Ch := make(chan int)
    t2Ch := make(chan int)

    Walk(t1, t1Ch)
    Walk(t2, t2Ch)
    output := make(chan bool)
    go func() {
        n1 := <-t1Ch
        n2 := <-t2Ch
        output <- n1 == n2
    }()
    return <-output

}

func main() {
    fmt.Println((&root, &root1))
}

Note:: U can find the full description here https://go.dev/tour/concurrency/7

Answer 1

First of all, you should close your channels when finished walking the tree. This could be accomplished by seperating out your recursive function like so:

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    if t != nil {
        ch <- t.Value
        walkRecursively(t.Left, ch)
        walkRecursively(t.Right, ch)
    }
    
}

func walkRecursively(t *tree.Tree, ch chan int) {
    if t != nil {
        ch <- t.Value
        walkRecursively(t.Left, ch)
        walkRecursively(t.Right, ch)
    }
}

Now your Same() function can range over the two channels and know when the work is done:

func Same(t1, t2 *tree.Tree) bool {

    // two channels for walking over two trees
    ch1 := make(chan int)
    ch2 := make(chan int)
    
    // two integer slices to capture two results
    sequence1 := []int{}
    sequence2 := []int{}
    
    // two go routines to push values to the channels
    // IMPORTANT! these must be go routines
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    
    // range over the channels to populate the sequence vars
    for n1 := range ch1 {
        sequence1 = append(sequence1, n1)   
    }
    for n2 := range ch2 {
        sequence2 = append(sequence2, n2)   
    }

    // since trees are randomly structured, we sort
    sort.Ints(sequence1)
    sort.Ints(sequence2)

    // slicesAreEqual is a helper function
    return slicesAreEqual(sequence1, sequence2)
}

Your helper function might look something like this:

func slicesAreEqual(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }
    return true
}