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.

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.