A Tour of Go Exercises

equivalent-binary-tree-search.go

// Exercise: Equivalent Binary Trees (https://tour.golang.org/concurrency/7)
// There can be many different binary trees with the same sequence of values stored in it.
// 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.

package main

import (
	"fmt"
	"log"
	"sort"
	"time"

	"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) {
	ch <- t.Value
	if t.Left != nil {
		go Walk(t.Left, ch)
	}
	if t.Right != nil {
		go Walk(t.Right, ch)
	}
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	var t1Values, t2Values []int
	t1c, t2c := make(chan int, 10), make(chan int, 10)
	go Walk(t1, t1c)
	go Walk(t2, t2c)
	for i := 0; i < 10; i++ {
		t1Values = append(t1Values, <-t1c)
		t2Values = append(t2Values, <-t2c)
	}
	sort.Ints(t1Values)
	sort.Ints(t2Values)
	for i, v := range t1Values {
		if v != t2Values[i] {
			return false
		}
	}
	return true
}

func main() {
	t1 := tree.New(1)
	t2 := tree.New(1)
	start := time.Now()
	same := Same(t1, t2)
	elapsed := time.Since(start)
	if same {
		fmt.Println("The two trees contain the same values!")
	} else {
		fmt.Println("The two trees do not contain the same values.")
	}
	log.Printf("Calculated in %s", elapsed)
}