Go Tour Exercise: Equivalent Binary Trees

An elegant solution using closure was presented in the golang-nuts group,

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch) // <- closes the channel when this function returns
    var walk func(t *tree.Tree)
    walk = func(t *tree.Tree) {
        if t == nil {
            return
        }
        walk(t.Left)
        ch <- t.Value
        walk(t.Right)
    }
    walk(t)
}

You could use close() if your Walk function doesn't recurse on itself. i.e. Walk would just do:

func Walk(t *tree.Tree, ch chan int) {
    walkRecurse(t, ch)
    close(ch)
}

Where walkRecurse is more or less your current Walk function, but recursing on walkRecurse. (or you rewrite Walk to be iterative - which, granted, is more hazzle) With this approach, your Same() function have to learn that the channels was closed, which is done with the channel receive of the form

k, ok1 := <-ch
g, ok2 := <-ch

And take proper action when ok1 and ok2 are different, or when they're both false

Another way, but probably not in the spirit of the exercise, is to count the number of nodes in the tree:

func Same(t1, t2 *tree.Tree) bool {
    countT1 := countTreeNodes(t1)
    countT2 := countTreeNodes(t2)
    if countT1 != countT2 {
        return false
    }
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for i := 0; i < countT1; i++ {
        if <-ch1 != <-ch2 {
            return false
        }
    }
    return true
}

You'll have to implement the countTreeNodes() function, which should count the number of nodes in a *Tree

Here's the full solution using ideas here and from the Google Group thread

package main

import "fmt"
import "code.google.com/p/go-tour/tree"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    var walker func(t *tree.Tree)
    walker = func (t *tree.Tree) {
        if (t == nil) {
            return
        }
        walker(t.Left)
        ch <- t.Value
        walker(t.Right)
    }
    walker(t)
    close(ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1, ch2 := make(chan int), make(chan int)

    go Walk(t1, ch1)
    go Walk(t2, ch2)

    for {
        v1,ok1 := <- ch1
        v2,ok2 := <- ch2

        if v1 != v2 || ok1 != ok2 {
            return false
        }

        if !ok1 {
            break
        }
    }

    return true
}

func main() {
    fmt.Println("1 and 1 same: ", Same(tree.New(1), tree.New(1)))
    fmt.Println("1 and 2 same: ", Same(tree.New(1), tree.New(2)))

}