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

The same function must check whether t1 and t2 have the same values in any order. The implementation returns instead, whether the order is of the elements the same in both parameters.

The requirement specifically states:

constructs a randomly-structured (but always sorted) binary tree

So, the solutions provided are all correct; they rely on the tree always being sorted. Not much use for a binary tree if it wouldn't be, anyhow

package main

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

// 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)
	var tree1, tree2 []int

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

	tr1, tr2 := 0, 0
	for i := 0; i < 20; i++ {
		select {
			case tr1 = <- ch1:
				tree1 = append(tree1, tr1)
			case tr2 = <- ch2:
				tree2 = append(tree2, tr2)
		}
	}
	return reflect.DeepEqual(tree1, tree2)
}

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

  package main
  
  import (
	  "golang.org/x/tour/tree"
	  "fmt"
  )
  
  func WalkInternal(t *tree.Tree, ch chan int) {
	  if t== nil {
		  return
	  }
	  
	  WalkInternal(t.Left, ch)
	  
	  ch <- t.Value
	  //fmt.Println(t.Value)
	  
	  WalkInternal(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) {
	  WalkInternal(t,ch)
	  close(ch)
  }
  
  // Same determines whether the trees
  // t1 and t2 contain the same values.
  func Same(t1, t2 *tree.Tree) bool {
	  tc1 := make(chan int, 10)
	  tc2 := make(chan int, 10)
	  
	  go Walk(t1, tc1)
	  go Walk(t2, tc2)
	  
	  for{
		  select{
			  case te1, ok1 := <-tc1:
				  te2, ok2 := <-tc2
				  if ok1 == ok2 {
					  //all done - chan closed
					  if ok1 == false { 
						  fmt.Println("same") 
						  return true
					  }
					  
					  //value not same, no need to sort as we read from a sorted tree
					  if te1 !=te2 { 
						  fmt.Println("not same") 
						  return false
					  } 
					  //fmt.Println("same:", te1, te2)
					  continue
				  }else{
					  fmt.Println("not same")  //not same length
					  return false
				  }
			  
		  }
	  }
	  
	  //return same
  }
  
  func main() {
	  Same(tree.New(1), tree.New(1)) 
	  Same(tree.New(1), tree.New(2)) 
	  Same(tree.New(2), tree.New(2)) 
  }

@Sebastian-Nielsen Great solution but I believe you meant:

noMoreValuesInEitherTree := !(ok1 || ok2) // !ok1 && !ok2
isMoreNodesInOneTree     := !(ok1 && ok2) // !ok1 || !ok2

here:

		   noMoreValuesInEitherTree := !(ok1 && ok2)
		if noMoreValuesInEitherTree {
			return true
		}
		
		   isMoreNodesInOneTree := !(ok1 || ok2)
		if isMoreNodesInOneTree {
			return false
		}

I tested with trees of uenequal lengths (or one nil):

func TestSame(t *testing.T) {
	tree1 := tree.New(1)
	tree2 := tree.New(2)
	treeSingle := &tree.Tree{Left: nil, Value: 42, Right: nil}
	cases := []struct {
		t1, t2   *tree.Tree
		expected bool
	}{
		{tree1, tree1, true},
		{tree1, tree2, false},
		{nil, tree1, false},
		{tree2, nil, false},
		{tree2, treeSingle, false},
	}

	for _, c := range cases {
		got := Same(c.t1, c.t2)
		if got != c.expected {
			t.Errorf("\nt1=%v\nt2=%v\n...returned %v, expected %v", c.t1, c.t2, got, c.expected)
		}
	}
}

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(t *tree.Tree, ch chan int)
	_Walk = func(t *tree.Tree, ch chan int) {
		if t != nil {
			_Walk(t.Left, ch)
			ch <- t.Value
			_Walk(t.Right, ch)
		}
	}
	_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, ch2 := make(chan int), make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	for {
		v1, ok1 := <-ch1
		v2, ok2 := <-ch2

		if (ok1 || ok2) == false {
			return true
		} else if (ok1 && ok2) == false || v1 != v2 {
			return false
		}
	}
}

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

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

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

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){
	_Walk(t, ch)
	close(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 Same(t1, t2 *tree.Tree) bool{
	ch1 := make(chan int, 10)
	ch2 := make(chan int, 10)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	for v := range ch1 {
		v2, ok := <-ch2
		if v != v2 || ! ok{
			return false
		}	
	}
	if _, ok := <-ch2; ok {
		return false
	}
	return true
}

func main() {
	t := tree.New(1)
	ch := make(chan int, 1000)
	go Walk(t, ch)
	for r := range ch {
		fmt.Println(r)
	}
	fmt.Println(Same(tree.New(1), tree.New(1)))
}

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

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

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	t1Values := make(map[int]int)
	
	myChanForT1 := make(chan int)
	go Walk(t1, myChanForT1)
	
	for i := range myChanForT1{
		t1Values[i] = 1
	}
	
	myChanForT2 := make(chan int)
	go Walk(t2, myChanForT2)
	
	for j := range myChanForT2{
		if _, ok := t1Values[j] ; ok == false {
			return false
		}
	}
	
	return true
}

func main() {
	fmt.Println(Same(tree.New(1), 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))	
}