Go Tour Exercise #7: Binary Trees equivalence

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?

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

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

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

This is how I did it, the difference is that you can wrap Walk into anonymous function and defer close(ch) inside it. Thus you have not to define other named recursive function

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, ch2 := make(chan int), make(chan int)
	go func() {
		defer close(ch1)
		Walk(t1, ch1)
	}()
	go func() {
		defer close(ch2)
		Walk(t2, ch2)
	}()
	for {
		v1, ok1 := <- ch1
		v2, ok2 := <- ch2
		if ok1 != ok2 || v1 != v2 {
			return false
		}
		if !ok1 && !ok2 {
			break
		}
	}
	return true
}

func main() {
	ch := make(chan int)
	go func () {
		defer close(ch)
		Walk(tree.New(3), ch)
	}()
	for i := range ch {
		fmt.Println(i)
	}
	
	fmt.Println(Same(tree.New(1), tree.New(1)))
	fmt.Println(Same(tree.New(1), tree.New(2)))
	fmt.Println(Same(tree.New(10), tree.New(10)))
}

While my first intuition was to also wrap the recursive walk and closing the channels, I felt it was not in the spirit of the exercise.

The exercise text contains the following information:

> The function tree.New(k) constructs a randomly-structured (but always sorted) binary tree holding the values k, 2k, 3k, ..., 10k.

Which clearly states that the resulting trees have exactly 10 nodes.

Therefore, in the spirit and simplicity of this exercise, I went with the following solution:

package main

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

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 Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)

	defer close(ch1)
	defer close(ch2)

	go Walk(t1, ch1)
	go Walk(t2, ch2)
	
	for i := 0; i < 10; i++ {
		if <-ch1 != <-ch2 {
			return false
		}
	}

	return true
}

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

If the goal would be to run on arbitrarily sized trees, then reacting to closed channels is the better solution, but I felt this was a simple exercise with intentionally put constraints to make it easier for the new Gopher.

This is my solution.

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,ch2 := make(chan int),make(chan int)
	
	go func() {
		Walk(t1, ch1)
		close(ch1)
	}()
	
	go func() {
		Walk(t2, ch2)
		close(ch2)
	}()
	
	for {
		v1, ok1 := <- ch1
		v2, ok2 := <- ch2
		
		if ok1 == false && ok2 == false {
			return true
		}
		
		if v1 != v2 {
			return false
		}
	}

	return false
}

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

Use goroutine with an anonymous function

go func() {
    .... // logic
    close(ch)// last close channel or defer close channel
    // do not use close() outside of goroutine
}()

Here's code which can read easy

Walk func

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 func

func Same(t1, t2 *tree.Tree) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)

    go func() {
	    Walk(t1, ch1)
		close(ch1)
	    }()
    }()


    go func() {
		Walk(t2, ch2)
		close(ch2)
		}()
	}()

    for {
	    v1, ok1 := <- ch1
	    v2, ok2 := <- ch2
	
	    if !ok1 && !ok2 {
	        // both closed at the same time (and all values until now were equal)
		    return true
	    }
	
	    if !ok1 || !ok2 || v1 != v2 {
		    return false
	    }
    }
    return true
}

main func

func main() {
    c := make(chan int)
    t1 := tree.New(1)
    go func() {
	    Walk(t1, c)
	    close(c)
    }()

    for i := range c {
	    fmt.Print(i) // 12345678910
    }

    fmt.Println("")
    result1 := Same(tree.New(1), tree.New(1))
    fmt.Println(result1) // true
    result2 := Same(tree.New(1), tree.New(2))
    fmt.Println(result2) // false
}

This is my solution. It properly checks for differences in the length of the two sequences.

package main

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

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

func Same(t1, t2 *tree.Tree) bool {
    chana := make (chan int)
    chanb := make (chan int)

    go Walk(t1, chana)
    go Walk(t2, chanb)

    for {
	    n1, ok1 := <-chana
        n2, ok2 := <-chanb        
        if n1 != n2 || ok1 != ok2 {
            return false
        }
        if (!ok1) {
            break
        }
    }
    return true; 
}

You got it almost right, there's no need to use the select statement because you will go through the default case too often, here's my solution that works without needing to count the number of nodes in the tress:

func Same(t1, t2 *tree.Tree) bool {
    ch1, ch2 := make(chan int), make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for i := range ch1 {
        j, more := <-ch2
        if more {
            if i != j { return false }
        } else { return false }
    }

    return true
}

Tried to solve this problem using map structure.

func Same(t1, t2 *tree.Tree) bool {
	countMap := make(map[int]int)
	ch := make(chan int)
	go Walk(t1, ch)
	for v := range ch {
		countMap[v]++
	}
	ch = make(chan int)
	go Walk(t2, ch)
	for v := range ch {
		countMap[v]--
		if countMap[v] < 0 {
			return false
		}
	}
	return true
}

All of previous answers do not solve the task about Same function. The question is:

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same2(t1, t2 *tree.Tree) bool

It shouldn't consider structure of tree. That's why following tests fail, gives us false in both lines:

fmt.Println("Should return true:", Same(tree.New(1), tree.New(1)))
fmt.Println("Should return false:", Same(tree.New(1), tree.New(2)))

Remember? > The function tree.New(k) constructs a randomly-structured (but always sorted) binary tree holding the values k, 2k, 3k, ..., 10k.

You need just check that both trees have the same values. And task description clearly notice that:

Same(tree.New(1), tree.New(1)) should return true, and Same(tree.New(1), tree.New(2)) should return false.

So to solve the task you need buffer all results from one tree and check does the values from second tree are in the first one.

Here is my solution, it's not ideal one :) :

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

	var tv1 = []int{}

	for v := range ch1 {
		tv1 = append(tv1, v)
	}

	inArray := func(arr []int, value int) bool {
		for a := range arr {
			if arr[a] == value {
				return true
			}
		}
		return false
	}

	for v2 := range ch2 {
		if !inArray(tv1, v2) {
			return false
		}
	}

	return true
}

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 {
		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, ch2 := make(chan int), make(chan int)
	go func() { Walk(t1, ch1); close(ch1) }()
	go func() { Walk(t2, ch2); close(ch2) }()
	for v1 := range ch1 {
		if v1 != <-ch2 {
			return false
		}
	}
	return true
}

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

You should avoid to let opened channels unattended or a thread can be waiting forever and never ending.

package main

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

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

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	var ch1, ch2 chan int = make(chan int), make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	
	ret := true
	for {
		v1, ok1 := <- ch1
		v2, ok2 := <- ch2
		
		if ok1 != ok2 {
			ret = false
		}
		if ok1 && (v1 != v2) {
			ret = false
		}
		if !ok1 && !ok2 {
			break
		}
	}
	
	return ret
}

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

My version

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 WalkRec(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}
	WalkRec(t.Left, ch)
	ch <- t.Value
	WalkRec(t.Right, ch)
}

func Walk(t *tree.Tree, ch chan int) {
	WalkRec(t, ch)
	close(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 {
		x, okx := <-ch1
		y, oky := <-ch2
		switch {
		case okx != oky:
			return false
		case x != y:
			return false
		case okx == oky && okx == false:
			return true
		}

	}

}

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

I wrote 2 versions that always read both channels to the end:

package main

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

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

func Same(t1, t2 *tree.Tree, sameChan func(ch1, ch2 chan int) bool) bool {
	ch1, ch2 := make(chan int), make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)

	return sameChan(ch1, ch2)
}

func sameChan1(ch1, ch2 chan int) bool {
	areSame := true
	for {
		v1, ok1 := <-ch1
		v2, ok2 := <-ch2

		if !ok1 && !ok2 {
			return areSame
		}

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

func sameChan2(ch1, ch2 chan int) bool {
	areSame := true
	for v1 := range ch1 {
		v2, ok2 := <-ch2

		if !ok2 || v1 != v2 {
			areSame = false
		}
	}
	for _ = range ch2 {
		areSame = false
	}
	return areSame
}

func main() {
	fmt.Println(Same(tree.New(1), tree.New(1), sameChan1))
	fmt.Println(Same(tree.New(2), tree.New(1), sameChan1))
	fmt.Println(Same(tree.New(1), tree.New(2), sameChan1))

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

That's how I did it using Inorder Traversal

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 {
		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 {
	c1, c2 := make(chan int), make(chan int)
	go Walk(t1, c1)
	go Walk(t2, c2)
	if <-c1 == <-c2 {
		return true
	} else {
		return false
	}
}

func main() {
	t1 := tree.New(1)
	t2 := tree.New(8)
	fmt.Println("the two trees are same?", Same(t1, t2))
}

because the question just said the tree just 10 nodes，then following is my answer after read other answers：

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

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

func Same(t1, t2 *tree.Tree) bool {
	ch1, ch2 := make(chan int), make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)

	for range make([]struct{}, 10) {
		if <-ch1 != <-ch2 {
			return false
		}
	}
	return true
}

Here's a solution that doesn't depend on differing tree lengths, neither does it depend on traversal order:

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) {
	var walk func(*tree.Tree)
	walk = func(tr *tree.Tree) {
		if tr == nil {
			return
		}

		walk(tr.Left)
		ch <- tr.Value
		walk(tr.Right)
	}

	walk(t)
	close(ch)
}

func merge(ch chan int, m map[int]int) {
	for i := range ch {
		count, ok := m[i]
		if ok {
			m[i] = count + 1
		} else {
			m[i] = 1
		}
	}
}

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

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

	merge(ch1, m)
	merge(ch2, m)

	for _, count := range m {
		if count != 2 {
			return false
		}
	}

	return true
}

For whoever interested, if you wonder how to solve this without creating a separate recursive function, here is an answer using a stack:

func Walk(t *tree.Tree, ch chan int) {
	defer close(ch)
	visitStack := []*tree.Tree{t}
	visited := make(map[*tree.Tree]bool, 1)
	for len(visitStack) > 0 {
		var n *tree.Tree
		n, visitStack = visitStack[len(visitStack)-1], visitStack[:len(visitStack)-1]
		if visited[n] {
			ch <- n.Value
			continue
		}
		if n.Right != nil {
			visitStack = append(visitStack, n.Right)
		}
		visitStack = append(visitStack, n)
		if n.Left != nil {
			visitStack = append(visitStack, n.Left)
		}
		visited[n] = true
	}
}

A clear answer:

package main

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

func WalkATree(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 {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go WalkATree(t1, ch1)
    go WalkATree(t2, ch2)
    var v1, v2 int
    var ok1, ok2 bool
    for {
        v1, ok1 = <- ch1
        v2, ok2 = <- ch2
        if !ok1 && !ok2 {
            return true
        }
        if !ok1 && ok2 || ok1 && !ok2 {
            return false
        }
        if v1 != v2 {
            return false
        }
    }
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(1)))
}

Here's my solution, without the defer magic. I thought this would be a bit easier to read, so it would worth sharing :)

Bonus: This version actually solves the problem in the tour's exercise and gives proper results.

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) {
	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 {
	var br bool
	ch1, ch2 := make(chan int), make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)

	for i:= range ch1 {
		if i == <-ch2 {
			br = true
		} else {
			br = false
			break
		}
	}
	return br
}

func main() {
	ch := make(chan int)
	go Walk(tree.New(1), ch)
	
	for i := range ch {
		fmt.Println(i)
	}
	
	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)))
}

So the output is as follows:

1
2
3
4
5
6
7
8
9
10
false
true
false

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) {
	walkRecursive(t, ch)
	close(ch)
}

func walkRecursive(t *tree.Tree, ch chan int) {
	if t == nil {
		return
	}
	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 := make(chan int)
	ch2 := make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)

	for {
		v1, ok1 := <-ch1
		v2, ok2 := <-ch2
		if ok1 != ok2 {
			return false
		}
		if !ok1 {
			return true
		}
		if v1 != v2 {
			return false
		}
	}
}

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

Haven't seen it so far in this thread. I used the nil channel technique presented in just for func

The issue with closing the channels was solved by kicking them off in an goroutine iife.

I think I could check more performant for equality though.

package main

import (
	"fmt"
	"reflect"
	"sort"

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

}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {

	c1 := make(chan int)
	s1 := []int{}

	go func() {
		Walk(t1, c1)
		close(c1)
	}()

	c2 := make(chan int)
	s2 := []int{}

	go func() {
		Walk(t2, c2)
		close(c2)
	}()

	for c1 != nil || c2 != nil {
		select {
		case v, ok := <-c1:
			if !ok {
				c1 = nil
				sort.Ints(s1)
				continue
			}
			s1 = append(s1, v)
		case v, ok := <-c2:
			if !ok {
				c2 = nil
				sort.Ints(s2)
				continue
			}
			s2 = append(s2, v)
		}
	}
	return reflect.DeepEqual(s1, s2)
}

func main() {
	fmt.Println(Same(tree.New(1), tree.New(1)))
}

If one is using recursive calls with one's Walk logic and one wishes to signal channel-consumers that there are no more items, it seems that one can put the majority of one's Walk logic into a second function, invoke that second function, wait for it to complete, then close the channel.

In the example below, the second ("inner Walk") function is a "closure" directly inside the Walk function, but it needn't be.

package main

import "golang.org/x/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) {
	defer close(ch)
	var iw func(*tree.Tree)
	iw = func(it *tree.Tree) {
		if it == nil {
			return
		}
		iw(it.Left)
		ch <- it.Value
		iw(it.Right)
	}
	iw(t)
}

// 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 {
		v1, more1 := <- ch1
		v2, more2 := <- ch2
		if (!more1 && !more2) {
			return true
		}
		if more1 != more2 || v1 != v2 {
			return false
		}
	}
}

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

Here's a non-recursive solution (i.e. won't have stack space issues on large inputs) that also does not require a separate visited map - it just uses a single Stack data structure. The trick to avoiding a visited map is to remove the visited entries from the stack and instead create new tree.Tree instances for the visited entries, with the Left side removed so it doesn't revisit the left side.

package main

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

func Pop(stack []*tree.Tree) (*tree.Tree, []*tree.Tree) {
	last := len(stack) - 1
	node := stack[last]
	stack[last] = nil
	return node, stack[:last]
}

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	defer close(ch)
	stack := []*tree.Tree{t}
	var node *tree.Tree
	for len(stack) > 0 {
		node, stack = Pop(stack)
		if node.Left != nil {
			stack = append(stack, &tree.Tree{nil, node.Value, node.Right}, node.Left)
			continue
		}

		ch <- node.Value

		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
}

// 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 {
			return false
		}
		if !ok1 || !ok2 {
			return ok1 == ok2
		}
	}
}

func PrintTree(t *tree.Tree) {
	ch := make(chan int)
	go Walk(t, ch)
	for i := range ch {
		fmt.Printf("%d ", i)
	}
	fmt.Println()
}

func main() {
	PrintTree(tree.New(1))
	PrintTree(&tree.Tree{Value: 1, Right: &tree.Tree{Value: 2}})

	fmt.Println("1 and 2 same (false): ", Same(tree.New(1), tree.New(2)))
	fmt.Println("1 and 1 same (true): ", Same(tree.New(1), tree.New(1)))
	fmt.Println("empty same (true): ", Same(&tree.Tree{}, &tree.Tree{}))
	fmt.Println("diff length same (false): ", Same(&tree.Tree{Value: 1}, &tree.Tree{Value: 2, Left: &tree.Tree{Value: 2}}))
}

The output is:

1 2 3 4 5 6 7 8 9 10 
1 2 
1 and 2 same (false):  false
1 and 1 same (true):  true
empty same (true):  true
diff length same (false):  false

How about just change count of incoming arguments by a little?

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	t1_map := map[int]int{}
	t2_map := map[int]int{}
	t1_ch := make(chan int)
	t2_ch := make(chan int)
	
	go Walk(t1, t1_ch, false)
	go Walk(t2, t2_ch, false)
	
	for value := range t1_ch {
		t1_map[value]++
	}
	
	for value := range t2_ch {
		t2_map[value]++
	}
	
	if len(t1_map) != len(t2_map) {
		return false
	}
	
	for t1_key, t1_value := range t1_map {
		t2_value, t2_exists := t2_map[t1_key]
		
		if (!t2_exists) || (t1_value != t2_value) {
			return false
		}
	}
	
	return true
}

func main() {
	t1 := tree.New(1)
	t2 := tree.New(2)
	t3 := tree.New(1)
	
	fmt.Println(Same(t1, t2))
	fmt.Println(Same(t1, t3))
	fmt.Println(Same(t3, t2))
}

In the author's case, they should just change the Same function to avoid an infinite loop:

func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
    ch2 := make(chan int)

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

	if <-ch1 != <-ch2 {
		return false
	}

    return true
}

This can be solved using an iterative approach (which will save on memory). Using an iterative approach based on this example:

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	stack := make([]*tree.Tree, 0)
	for {
		if t != nil {
			stack = append(stack, t)
			t = t.Left
		} else if(len(stack) > 0) {
			lastIndex := len(stack) - 1
			t = stack[lastIndex]
			stack = stack[:lastIndex]
			
			ch <- t.Value
			
			t = t.Right
		} else {
			close(ch)
			return
		}
	}
}