A Tour of Go Exercises: Equivalent Binary Trees

For a new high-performance web project I’m working on, I decided to learn a new “low-level” language. After looking at Julia, Rust, and Go, I decided that for several reasons I would go with… Go. To get familiar with the idiom I’ve been reading through the docs and going through the excellent A Tour of Go online tutorial. One of the exercises in that tutorial involves comparing two binary trees using Go’s lightweight concurrent programming construct, the goroutine.

I ran into an interesting issue while writing this routine so I decided to post my solution. You can try the exercise here before opening the spoiler to see my code below.

package main

import (
	"fmt"

	"golang.org/x/tour/tree"
)

func Walk(root *tree.Tree, ch chan int) {
	var worker func(t *tree.Tree)

	worker = func(t *tree.Tree) {
		if t.Left != nil {
			worker(t.Left)
		}

		ch <- t.Value
		if t.Right != nil {
			worker(t.Right)
		}
	}

	worker(root)
	close(ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)

	go Walk(t1, ch1)
	go Walk(t2, ch2)

	for v1 := range ch1 {
		v2 := <-ch2

		if v1 != v2 {
			return false
		}
	}

	return true
}

func main() {
	ch := make(chan int)
	go Walk(tree.New(1), ch)

	for v := range ch {
		fmt.Println(v)
	}

	fmt.Println("Same(tree.New(1), tree.New(1))", Same(tree.New(1), tree.New(1)))
	fmt.Println("Same(tree.New(1), tree.New(2))", Same(tree.New(1), tree.New(2)))
}

So the solution is fairly straightforward. The Walk() function does an inorder traversal of the tree while writing the values to the given channel. My first solution had the Walk() function calling itself recursively, but I ran into problems when I wanted to close() the channel after the last node was visited.

The obvious solution was to use a closure and a nested function to do the traversal, but due to the way that variables are declared in Go I couldn’t just assign an anonymous function to a variable and then reference it directly. So I was forced to declare the variable on line 10 then assign the anonymous function to it on line 12.

There is still one (known) issue with this solution, it doesn’t deal with binary trees with a different number of nodes. I was too lazy to rewrite the test case generation code to generate valid test cases, so I’ll leave that as an exercise for you, gentle reader!