Compare two binary trees using Goroutines

BinaryTreeCompare.go

package main

// solution to exercise from https://tour.golang.org/concurrency/7
// if running local, execute `go get golang.org/x/tour/tree` beforehand

import (
	"fmt"

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

//Walk Inorder Depth-First-Search
func Walk(t *tree.Tree, ch chan int, quit chan bool) {
	node := t // the current node's pointer
	stack := []*tree.Tree{}
	for {
		if node != nil {
			stack = append(stack, node)
			node = node.Left
		} else if len(stack) > 0 {
			var parent *tree.Tree
			parent, stack = stack[len(stack)-1], stack[:(len(stack)-1)] // pop back the top node in stack & go right
			ch <- parent.Value                                          // signal a tree traversal event
			node = parent.Right
		} else { // done! send something to `quit` to signal a return
			quit <- true
			return
		}
	}
}

// Same determines whether the trees t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree, success chan bool) bool {
	channel1 := make(chan int) // create channels with default buffer size 0
	channel2 := make(chan int)
	quitSignal := make(chan bool) // a "bridge" channel to receive the done event from above channels

	go Walk(t1, channel1, quitSignal) // kick off the Goroutine in a Green Thread
	go Walk(t2, channel2, quitSignal)

	for { // create a loop to listen to the communication channel with the above Goroutine
		select {
		case v1 := <-channel1: // receive a value from channel 1, then block `channel 1` (as it does not have a buffer specified)
			v2 := <-channel2 //receive another value from Goroutine 2 to compare, then block `channel 2`
			if v1 != v2 {
				success <- false
				return false
			}
		case <-quitSignal:
			success <- true
			return true
		}
		// now we're out of the current "select"
		// the next iteration, with new "select" statement, will unblock the channels, and receive 1 new value from each of them
	}
}

func main() {
	tree1 := tree.New(2) // create a new tree
	tree2 := tree.New(1)
	signal := make(chan bool)

	go Same(tree1, tree2, signal) // kick of the comparison in another Goroutine
	success := <-signal           // pause the main thread until signal received
	fmt.Println(success)          // should print False
}

What I learned

There are no "references" in go. All function parameters are copied to the new stack frame, meaning all parameters are just copies of the original self. For example:

func main() {
	value := "Hello, playground"
	addr := &value // use the ampersand [&] syntax to retrieve the physical address
	
	tryChange(addr) // NOT WORKING
	fmt.Println(addr) // 0xc0000961e0
	fmt.Println(*addr) // still is "Hello, playground"
	
	tryModify(addr) // WORKS!
	fmt.Println(addr) // 0xc0000961e0
	fmt.Println(*addr) // "Goodbye, playground"
	
	// as you can see, the physical address stays the same, but the content inside is modified
}

func tryChange(p *string) {
	// as `p` is a copy, overwriting it won't change the original
	t := "test"
	p = &t
}

func tryModify(p *string) {
	//2 operations:
	//  1. deference - get the pointed value from the physical address that is passed in (using the asterisk [*] syntax)
	//  2. overwrite - the pointed value with a new string
	*p = "Goodbye, playground"
}

In Go, you can actually assign "nil" to pointers, but not concrete variables

	value := "Hello, playground" // can not do `value := nil`, must initialize value
	addr := &value
	addr = nil // `addr` is now unrelated to `value` as it is reassigned to special address 0x0 (which "nil" represents)
	fmt.Println(addr) // <nil>
	fmt.Println(value) // "Hello, playground"
	fmt.Println(*addr) // runtime error: nil pointer dereference

Golang has not seems to implemented any solutions for the billion dollar mistake