巡回练习：等效二叉树

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?

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 walkRecurseis 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'l have to implement the countTreeNodes()function, which should count the number of nodes in a *Tree

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

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
}

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

}

Here's the solution I came up with :

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

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

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

    for i:=range ch {
        j,ok:=<-dh
        if(i!=j||!ok)  {return false} 
    }

    return true
}

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
}

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

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

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
}

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.

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
}