treewalk.go

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) {
	if t.Left != nil {
		Walk( t.Left, ch )
	}
	ch <-t.Value
	if t.Right != nil {
		Walk( t.Right, ch )
	}
}

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	// FIXME: we should also stop goroutines
	// when we no longer need them
	ch1 := make(chan int)
	go WalkNClose(t1, ch1);
	ch2 := make(chan int)
	go WalkNClose(t2, ch2);
	for {
		v1, ok1 := <-ch1;
		v2, ok2 := <-ch2;
		fmt.Print("got: v1=",v1," v2=",v2," ok1=",ok1," ok2=",ok2,": "); // debug
		switch {
		case ok1 != ok2:
			fmt.Println("different: size"); // debug
			return false
		case !ok1 && !ok2:
			fmt.Println("same"); // debug
			return true
		case v1 != v2:
			fmt.Println("different: not equal"); // debug
			return false
		default:
			fmt.Println("passed"); // debug
		}
	}
	panic("we can't be here")
}

func main() {
	//t1 := tree.New(1)
	t1 := &tree.Tree{
		&tree.Tree{
			&tree.Tree{nil,1,nil},
			1,
			&tree.Tree{nil,2,nil},
		},
		3,
		&tree.Tree{
			&tree.Tree{nil,5,nil},
			8,
			&tree.Tree{nil,13,nil},
		},
	}
	fmt.Println("t1=",t1)
	//t2 := tree.New(1)
	t2 := &tree.Tree{
		&tree.Tree{
			&tree.Tree{
				&tree.Tree{nil,1,nil},
				1,
				&tree.Tree{nil,2,nil},
			},
			3,
			&tree.Tree{nil,5,nil},
		},
		8,
		&tree.Tree{nil,13,nil},
	}
	fmt.Println("t2=",t2)
	if Same(t1, t2) {
		fmt.Println("t1 and t2 are the same")
	} else {
		fmt.Println("t1 and t2 are different");
	}
}

It's the exercise http://tour.golang.org/#70

The output:

t1= (((1) 1 (2)) 3 ((5) 8 (13)))
t2= ((((1) 1 (2)) 3 (5)) 8 (13))
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=2 v2=2 ok1=true ok2=true: passed
got: v1=3 v2=3 ok1=true ok2=true: passed
got: v1=5 v2=5 ok1=true ok2=true: passed
got: v1=8 v2=8 ok1=true ok2=true: passed
got: v1=13 v2=13 ok1=true ok2=true: passed
got: v1=0 v2=0 ok1=false ok2=false: same
t1 and t2 are the same

If we shorten the second tree:

t1= (((1) 1 (2)) 3 ((5) 8 (13)))
t2= ((((1) 1 (2)) 3 (5)) 8)
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=2 v2=2 ok1=true ok2=true: passed
got: v1=3 v2=3 ok1=true ok2=true: passed
got: v1=5 v2=5 ok1=true ok2=true: passed
got: v1=8 v2=8 ok1=true ok2=true: passed
got: v1=13 v2=0 ok1=true ok2=false: different: size
t1 and t2 are different

If we change last 13 to 3:

t1= (((1) 1 (2)) 3 ((5) 8 (13)))
t2= ((((1) 1 (2)) 3 (5)) 8 (3))
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=1 v2=1 ok1=true ok2=true: passed
got: v1=2 v2=2 ok1=true ok2=true: passed
got: v1=3 v2=3 ok1=true ok2=true: passed
got: v1=5 v2=5 ok1=true ok2=true: passed
got: v1=8 v2=8 ok1=true ok2=true: passed
got: v1=13 v2=3 ok1=true ok2=true: different: not equal
t1 and t2 are different