Exercise: Equivalent Binary Trees

tree.go

package main

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

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    WalkRecursive(t, ch)
    close(ch)
}

func WalkRecursive(t *tree.Tree, ch chan int) {
    if t != nil {
        WalkRecursive(t.Left, ch)
        ch <- t.Value
        WalkRecursive(t.Right, 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 {
        n1, ok1 := <- ch1
        n2, ok2 := <- ch2
        if ok1 != ok2 || n1 != n2 {
        	return false
        }
        if !ok1 {
        	break;
        }
    }
    return true
    
    
}

func main() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)
    fmt.Println(Same(tree.New(1), tree.New(2)))
    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(2), tree.New(1)))
    
}

package main

import (
	"golang.org/x/tour/tree"
	"fmt"
)

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	walkR(t, ch)
	close(ch)
}

func walkR(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}

	walkR(t.Left, ch)
	ch <- t.Value
	walkR(t.Right, ch)
}

func readChan(ch chan int) string {
	l := []int{}
	for v := range ch {
		l = append(l, v)
	}
	return fmt.Sprint(l)
}

// 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)
	s1, s2 := readChan(ch1), readChan(ch2)
	return s1 == s2
}

func main() {
	ch := make(chan int)
	go Walk(tree.New(1), ch)
	fmt.Println(readChan(ch))
	
	fmt.Println(Same(tree.New(1), tree.New(1)))
	fmt.Println(Same(tree.New(1), tree.New(2)))
}

package main

import (
	"fmt"

	"golang.org/x/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 == nil {
		close(ch)
		return
	}

	stack, cur := []*tree.Tree{}, t
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ch <- cur.Value
		cur = cur.Right
	}
	close(ch)
}

type counts struct {
	v1 int
	v2 int
}

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

	values := map[int]counts{}
	for n := 2; n > 0; {
		select {
		case v, ok := <-ch1:
			if !ok {
				n, ch1 = n-1, nil
			}
			c, ok := values[v]
			if !ok {
				values[v] = counts{1, 0}
			} else {
				c.v1++
				values[v] = c
			}
		case v, ok := <-ch2:
			if !ok {
				n, ch2 = n-1, nil
			}
			c, ok := values[v]
			if !ok {
				values[v] = counts{0, 1}
			} else {
				c.v2++
				values[v] = c
			}
		}
	}

	for _, c := range values {
		if c.v1 != c.v2 {
			return false
		}
	}
	return true
}

func main() {
	ch := make(chan int, 10)
	go Walk(tree.New(1), ch)
	for v := range ch {
		fmt.Println(v)
	}

	fmt.Println(Same(tree.New(1), tree.New(1)))
	fmt.Println(Same(tree.New(1), tree.New(2)))
}

package main

import (
	"golang.org/x/tour/tree"
	"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)
	}
	
	if t.Right != nil {
		Walk(t.Right, ch)
	}
	
	ch <- t.Value
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch := make(chan int, 20)
	go Walk(t1, ch)
	go Walk(t2, ch)
		
	res := 0
	for i := 0; i < 20; i++ {
		val := <-ch
		res ^= val
	}
	
	return res == 0
}

func main() {
	t1, t2 := tree.New(1), tree.New(1)
	fmt.Printf("%v\n%v\n%v\n*****\n", t1, t2, Same(t1, t2))	
	
	t1, t2 = tree.New(2), tree.New(3)
	fmt.Printf("%v\n%v\n%v\n*****\n", t1, t2, Same(t1, t2))	
}

package main

import (
	"golang.org/x/tour/tree"
	"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 == nil) { return }
	Walk(t.Left, ch)
	ch <- t.Value
	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 i := 0; i < cap(ch1); i++ {
		if (<-ch1 != <-ch2) { return false }
	}
	return true
}

func testWalk() {
	ch := make(chan int)
	go Walk(tree.New(1), ch)
	for i := 1; i < 11; i++ {
		if (i != <-ch) { 
			fmt.Println("Walk doesn't work")
			break
		}
	}
	fmt.Println("Walk does work")
}

func testSame() {
	if Same(tree.New(1), tree.New(1)) && Same(tree.New(1), tree.New(2)) {
	   	fmt.Println("Same does work")
	} else {
	   	fmt.Println("Same doesn't work")
	}
}

func main() {
	testWalk()
	testSame()
}

I believe this does not work. It says both functions work, but that seems to be due to two mistakes cancelling each other out.

Basically, the for loop in Same() uses i < cap(ch1) as an ending condition, which will never loop once as it is always false, due to cap(ch) always being 0 for an unbuffered channel ch. Thus, Same() always returns true no matter the input. Correct me if I'm wrong, though!

The reason it works is because in testSame() we test that both calls return true, when we would actually expect the second one to return false.