Go Tour Exercise #7: Binary Trees equivalence

Question

I am trying to solve equivalent binary trees exercise on go tour. Here is what I did;

package main  import "tour/tree" import "fmt"  // Walk walks the tree t sending all values // from the tree to the channel ch. func Walk(t *tree.Tree, ch chan int) {     if t.Left != nil {         Walk(t.Left, ch)     }     ch <- t.Value     if t.Right != nil {         Walk(t.Right, ch)     }  }  // Same determines whether the trees // t1 and t2 contain the same values. func Same(t1, t2 *tree.Tree) bool {     ch1 := make(chan int)     ch2 := make(chan int)     go Walk(t1, ch1)     go Walk(t2, ch2)     for k := range ch1 {         select {         case g := <-ch2:             if k != g {                 return false             }         default:             break         }     }     return true }  func main() {     fmt.Println(Same(tree.New(1), tree.New(1)))     fmt.Println(Same(tree.New(1), tree.New(2))) } 

However, I couldn't find out how to signal if any no more elements left in trees. I can't use close(ch) on Walk() because it makes the channel close before all values are sent (because of recursion.) Can anyone lend me a hand here?

Answer 1

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) } 

Answer 2

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)))  }