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

@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.