Skip to content

Instantly share code, notes, and snippets.

@kaipakartik
Created December 25, 2013 07:00
Show Gist options
  • Save kaipakartik/8120855 to your computer and use it in GitHub Desktop.
Save kaipakartik/8120855 to your computer and use it in GitHub Desktop.
Exercise: Equivalent Binary Trees
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)))
}
@kaen98
Copy link

kaen98 commented Apr 30, 2020

amazing! this help me!

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

func goWalk(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, 100)
	ch2 := make(chan int, 100)

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

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

		if (ok1 == false) {
			break;
		}
	}

	return true
}

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

@dilyanpalauzov
Copy link

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
Copy link

Sebastian-Nielsen commented Aug 25, 2021

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
Copy link

alexgoto commented Aug 28, 2021

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
Copy link

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

Copy link

ghost commented Oct 27, 2021

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
Copy link

FelixAnna commented Oct 28, 2021

  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
Copy link

@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
Copy link

noskcire11 commented May 9, 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) {
	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
Copy link

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
Copy link

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
Copy link

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
Copy link

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

@curbol
Copy link

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
Copy link

vvvitaly commented Jan 26, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment