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

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

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