Equivalent binary trees (A Tour of Go)

Question

Any suggestions on how to improve the code shown below for the Go-tour exercise?

Exercise description:

There can be many different binary trees with the same sequence of values stored at the leaves. A function to check whether two binary trees store the same sequence is quite complex in most languages. We'll use Go's concurrency and channels to write a simple solution.

This example uses the tree package, which defines the type:

type Tree struct {
 Left *Tree
 Value int
 Right *Tree
}

1. Implement the Walk function.

2. Test the Walk function.

   The function tree.New(k) constructs a randomly-structured binary tree holding the values k, 2k, 3k, ..., 10k.

   Create a new channel ch and kick off the walker:

   go Walk(tree.New(1), ch) Then read and print 10 values from the channel. It should be the numbers 1, 2, 3, ..., 10.

3. Implement the Same function using Walk to determine whether t1 and t2 store the same values.

4. Test the Same function.

   Same(tree.New(1), tree.New(1)) should return true, and Same(tree.New(1), tree.New(2)) should return false.

Code skeleton:

package main
import "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)
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool
func main() {
}

Solution:

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) {
 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 {
 c1 := make(chan int, 10)
 c2 := make(chan int, 10)
 go Walk(t1, c1)
 go Walk(t2, c2)
 for i := 0; i < 10; i++ {
 x, y := <-c1, <-c2
 fmt.Printf("x: %v, y: %v\n", x, y)
 if x != y {
 return false
 }
 }
 return true
}
func main() {
 fmt.Println(Same(tree.New(1), tree.New(1)))
 fmt.Println(Same(tree.New(1), tree.New(2)))
}

Answer 1

This is a nice answer to a fun challenge. There are a couple ways I can see to improve it.

1. This solution only works for arrays of up to 10 values due to the for loop terminating after 10 iterations. We can make it work for an arbitrary number of values by closeing the channel when Walk has complete, and testing for each channel's state to match.

2. Testing the value earlier in the walk will lead to earlier fails. Reordering the send on the channel to be first will allow this.

Here is a refactored version of your code:

func Walk(t *tree.Tree, vals chan int) {
 if t != nil {
 vals <- t.Value
 Walk(t.Left, vals)
 Walk(t.Right, vals)
 }
}
func Same(a, b *tree.Tree) bool {
 avals := make(chan int, 8)
 bvals := make(chan int, 8)
 go func() {
 Walk(a, avals)
 close(avals)
 }()
 go func() {
 Walk(b, bvals)
 close(bvals)
 }()
 for {
 av, aopen := <-avals
 bv, bopen := <-bvals
 if aopen != bopen || av != bv {
 return false
 }
 if !aopen {
 return true
 }
 }
}

Buffering the channels is still useful since synchronization is not a requirement for evaulation, so I've left them buffered.

• Legato: Welcome to CodeReview, Jason. The best first posts are definitely answers. Happy to have you.
• Ghost Bunnies: When I execute this example, I always fall through the if aopen != bopen || av != bv { return false } condition. Indeed there are good chances that av != bv is true as the function tree.New(k) constructs a randomly-structured binary tree holding the values k, 2k, 3k, ..., 10k. My question is, if @Jason's solution doesn't work, how come @P5sx's solution works? I can't quite grasp what's the fundamental difference in handling this problem.

Answer 2

Disclaimer: Not a go programmer

I think Walk could be written in a way such that it handles nil input. Then, this :

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

could be written

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

I'm not sure what the 10 corresponds to but it's probably be worth storing this in a constant to avoid having magic numbers in different places.