tree-compare.go

// Two binary trees may be of different shapes, 
// but have the same contents. For example:
//
//        4               6
//      2   6          4     7
//     1 3 5 7       2   5 
//                  1 3
//
// Go's concurrency primitives allow us to neatly
// traverse and compare the contents of two trees.

package main

import (
	"fmt"
	"rand"
)

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

// Walk traverses a tree depth-first, 
// sending each Value on a channel.
func Walk(t *Tree, ch chan int) {
	if t == nil {
		return
	}
	Walk(t.Left, ch)
	ch <- t.Value
	Walk(t.Right, ch)
}

// Walker launches Walk in a new goroutine,
// and makes and returns the value channel.
func Walker(t *Tree) chan int {
	ch := make(chan int)
	go func() {
		Walk(t, ch)
		close(ch)
	}()
	return ch
}

// Compare reads values from two Walker channels
// simultaneously, and returns true if t1 and t2 
// have the same contents.
func Compare(t1, t2 *Tree) bool {
	c1, c2 := Walker(t1), Walker(t2)
	for <-c1 == <-c2 {
		if closed(c1) != closed(c1) {
			return false
		}
		if closed(c1) && closed(c2) {
			return true
		}
	}
	return false
}

// New returns a new, random binary tree
// holding the values 1k, 2k, ..., nk.
func New(n, k int) *Tree {
	var t *Tree
	for _, v := range rand.Perm(n) {
		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)
		return t
	}
	t.Right = insert(t.Right, v)
	return t
}

func main() {
	t1 := New(1, 100)
	fmt.Println(Compare(t1, New(1, 100)), "Same Contents")
	fmt.Println(Compare(t1, New(1, 99)), "Differing Sizes")
	fmt.Println(Compare(t1, New(2, 100)), "Differing Values")
	fmt.Println(Compare(t1, New(2, 101)), "Dissimilar")
}