Instantly share code, notes, and snippets.

# kaipakartik/tree.go

Created December 25, 2013 07:00
Show Gist options
• Save kaipakartik/8120855 to your computer and use it in GitHub Desktop.
Exercise: Equivalent Binary Trees
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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))) }

### dilyanpalauzov commented Aug 8, 2021

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.

### Sebastian-Nielsen commented Aug 25, 2021 • edited

Always try to strive for clean and readable code

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

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

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

if v1 != v2 {
return false
}

// v1 and v2 exist and are equal to each other, so continue
}
}

func main() {
fmt.Println("Test 1 (expected true):",  Same(tree.New(1), tree.New(1)))
fmt.Println("Test 2 (expected false):", Same(tree.New(1), tree.New(2)))
}```

### alexgoto commented Aug 28, 2021 • edited

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

### BartRobeyns commented Oct 10, 2021

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

### ghost commented Oct 27, 2021 • edited by ghost

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

### FelixAnna commented Oct 28, 2021 • edited

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

### eugenius1 commented Nov 1, 2021

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

### noskcire11 commented May 9, 2022 • edited

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

### rotaryden commented Aug 31, 2022

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

### krapie commented Dec 13, 2022

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

### juspolo commented Jan 26, 2023

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

### xian-wen commented Feb 10, 2023

```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)
return s1 == s2
}

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(1), tree.New(2)))
}```

### curbol commented Jun 13, 2023

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

### vvvitaly commented Jan 26, 2024 • edited

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