Binary trees exercise

Question

I'm not sure about this code but it feels ugly to me. It is a solution to this.

package main

import ("golang.org/x/tour/tree"; "fmt"; "reflect"; "sort")

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

func WalkTest(t *tree.Tree, ch chan int) []int {
    go Walk(t, ch)
    var testSlice []int
    for i := 0; i <10; i++ {
        testSlice = append(testSlice, <- ch)
    }
    return testSlice
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    var t1Slice []int
    var t2Slice []int
    ch1 := make(chan int, 10)
    ch2 := make(chan int, 10)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for i := 0; i < 10; i++ {
        t1Slice = append(t1Slice, <- ch1)
        t2Slice = append(t2Slice, <- ch2)
    }
    sort.Ints(t1Slice); sort.Ints(t2Slice)
    return reflect.DeepEqual(t1Slice, t2Slice)
}

func main() {
    // Test the walk function
    walkTestTree := tree.New(1)
    walkTestCh := make(chan int, 10)
    walkTest := WalkTest(walkTestTree, walkTestCh)
    if len(walkTest) != 10 {
        panic("Walk test failed")
    }
    fmt.Println("Walk test ok!")

    // test the Same function
    testTree1 := tree.New(1)
    testTree2 := tree.New(1)
    sameTest := Same(testTree1, testTree2)
    if !sameTest {
        panic("same test failed")
    }
    fmt.Println("Same test passed")

    aTree := tree.New(1)
    bTree := tree.New(1)
    fmt.Println(Same(aTree, bTree))
}

Answer 1

The ugly

Not sure about this code but it feels ugly to me...

I agree :-)

The WalkTest function and other code that uses it is not pretty. This is not part of the exercise, not really well done, so practically it's just noise. It's not well done, because all it does is put values from the tree into a slice, return it, and then main checks that the length is 10. What does that mean? It's not a useful test.

I'm not a fan of variables for one-time use without justification. For example these:

testTree1 := tree.New(1)
testTree2 := tree.New(1)
sameTest := Same(testTree1, testTree2)
if !sameTest {
  panic("same test failed")
}

I would find the above easier to read without the one-time variables:

if !Same(tree.New(1), tree.New(1)) {
    panic("got false; expected true (same trees)")
}

Magic

In this code, why should the length of walkTest be 10?

walkTestCh := make(chan int, 10)
walkTest := WalkTest(walkTestTree, walkTestCh)
if len(walkTest) != 10 {
  panic("Walk test failed")
}

You create a buffered channel with size 10. But why buffered, and why 10? Then WalkTest does something, but just be reading this code, we have no clue that 10 has any special significance. Yet we expect the returned walkTest slice to have length of 10.

This could would have made a lot more sense if WalkTest took a count parameter. Then it would be reasonable to expect that a slice returned by WalkTest(tree, ch, 123) should have length = 123.

Variable declarations

In this code, t1Slice and t2Slice are declared at the top, but only used much later.

var t1Slice []int
var t2Slice []int
ch1 := make(chan int, 10)
ch2 := make(chan int, 10)
go Walk(t1, ch1)
go Walk(t2, ch2)
for i := 0; i < 10; i++ {
  t1Slice = append(t1Slice, <-ch1)
  t2Slice = append(t2Slice, <-ch2)
}

It would be better to declare them right before you need them:

ch1 := make(chan int, 10)
ch2 := make(chan int, 10)
go Walk(t1, ch1)
go Walk(t2, ch2)

var t1Slice []int
var t2Slice []int
for i := 0; i < 10; i++ {
    t1Slice = append(t1Slice, <-ch1)
    t2Slice = append(t2Slice, <-ch2)
}

Performance

The exercise includes a link to the documentation of Tree, from where you can find the source code too. As it turns out, the random binary tree is actually built as a binary search tree. The consequence of that is in this case if you traverse the nodes in in-order, you will get sorted values:

func Walk(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}

With that, testing the equivalence becomes simpler and more efficient, without needing intermediary slices, and sort.Ints and reflect.DeepEqual:

func Same(t1, t2 *tree.Tree) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)

    // as per the spec, a tree.Tree has 10 elements
    size := 10
    for i := 0; i < size; i++ {
        if <-ch1 != <-ch2 {
            return false
        }
    }
    return true
}

The "specs" I'm referring to is this btw:

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

Formatting

There is a standard formatting in Go, enforceable by the go fmt command. Simply run this command on your code, or use the Format button on the playground or on the tour.