check equivalence of b-trees

README.md

Solution to the golang tour's concurrency exercise testing for equivalent binary trees.

Compare with similiar solution presented in golangbootcamp's concurrency chapter.

---

There can be many different binary trees with the same sequence of values stored at the leaves. For example, here are two binary trees storing the sequence 1, 1, 2, 3, 5, 8, 13.

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.

tree.go

// Copyright 2011 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package tree

import (
	"fmt"
	"math/rand"
)

// A Tree is a binary tree with integer values.
type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

// New returns a new, random binary tree holding the values k, 2k, ..., 10k.
func New(k int) *Tree {
	var t *Tree
	for _, v := range rand.Perm(10) {
		t = insert(t, (1+v)*k)
	}
	return t
}

func insert(t *Tree, v int) *Tree {
	if t == nil {
		return &Tree{nil, v, nil}
	}
	if v < t.Value {
		t.Left = insert(t.Left, v)
	} else {
		t.Right = insert(t.Right, v)
	}
	return t
}

func (t *Tree) String() string {
	if t == nil {
		return "()"
	}
	s := ""
	if t.Left != nil {
		s += t.Left.String() + " "
	}
	s += fmt.Sprint(t.Value)
	if t.Right != nil {
		s += " " + t.Right.String()
	}
	return "(" + s + ")"
}

tree_test.go

package tree

import "testing"

type testCases []struct {
    a *Tree
    b *Tree
    want bool
}

func TestSame(t *testing.T) {
    cases := testCases{
        {New(1), New(1), true},
        {New(1), New(2), false},
    }   
    for _, c := range cases {
        if Same(c.a, c.b) != c.want {
            t.Errorf("Same(%q, %q) != %v", c.a, c.b, c.want)
        }
    }
}

walk.go

package tree

// Walk recursively walks the tree t sending all values from 
// the tree to the channel ch as found from left to right.
func Walk(t *Tree, ch chan int) {
    if t == nil {
        return
    }
    // walk the left side first
    Walk(t.Left, ch)
    // push the value to the channel
    ch <- t.Value
    // walk the right side last
    Walk(t.Right, ch)
}   

func Walker(t *Tree, ch chan int) {
    // initiate walking over tree t with corresponding channel
    Walk(t, ch)
    // close channel so that range can finish
    close(ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *Tree) bool {
    c1, c2 := make(chan int), make(chan int)
    go Walker(t1, c1)
    go Walker(t2, c2)
    for v1 := range c1 {
        v2, ok := <- c2
        if !ok {
            return false
        }   
        if v1 != v2 {
            return false
        }   
    }   
    return true
}   

What if t2 was a different sized tree?