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

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

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

I believe this does not work. It says both functions work, but that seems to be due to two mistakes cancelling each other out.

Basically, the for loop in Same() uses i < cap(ch1) as an ending condition, which will never loop once as it is always false, due to cap(ch) always being 0 for an unbuffered channel ch. Thus, Same() always returns true no matter the input. Correct me if I'm wrong, though!

The reason it works is because in testSame() we test that both calls return true, when we would actually expect the second one to return false.

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

sorted and balanced are different things. The functions written above do not work.
For example, the tree.New(1) function can return the following trees:

They are both sorted, but the structure is different. The functions written above return false for these two trees, although they should be true

@Trickster22 : No, both of your trees are no valid binary trees and therefore will never be returned by tree.New(). When the tree is build the rule for inserting a new value is: start at tree root -> if the new value is smaller or equal go to the left, otherwise go to the right -> repeat until you can't go further then insert new value there.

as you can see in your picture in the left tree node "2" and "1" are on the wrong position. both must be left to node "3". same for the right tree in your picture: node "2" cannot be placed there, it must be placed right to node "1".

The algorithm from post #1 does work for valid binary trees: It returns the left-most node first (= the lowest value), then the parent node (equal or greater value), then the parent's right subtree (all values are greater than the parent's value). if the right subtree is done the algorithm returns to the grandparent node, return it's value and then processes the grandparent's right sub tree. it does so until it has finally processed the root node's right subtree.