Go Tour Exercise #7: Walking the tree

I completed the go tour exercise for tree comparisons (#69) and was able to effectively compare two trees.

Here is the code

package main

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	c := make(chan int)
	c2 := make(chan int)
	go Walk(t1, c)
	go Walk(t2, c2)
	for i := 0; i < 10; i++ {
		if <-c != <-c2 {
			return false
		}
	}
	return true
}

func main() {
	fmt.Println(Same(tree.New(1), tree.New(1)))
}

The part that confuses me is that if I switch around the order of the commands in the walk function to be

    ch <- t.Value
    Walk(t.Right,ch)
    Walk(t.Left,ch)

the comparison no longer works. I tried printing out the results of Walk(tree.New(1),c) twice and oddly the first call printed

    10,5,7,9...

while the second call of Walk(tree.New(1),c) printed

    7,9,10,8...

Why does calling the same function twice result in two different outputs when switching the order of the walk commands?

First you need to understand the properties of the tree. The tree is setup so that a number to the Left is always less than the current node's value. A number to the Right is always more.

Therefore, if you wanted to find the smallest number, all you need to do is go "Left" at each node. If you go to the parent of the lowest number, you get the second lowest. The Right child of the second lowest may or may not be the third lowest. However, if you then take a Left at every chance from the Right child of the second lowest, you will end up at the third lowest. This is done until every node has been traversed.

When you Walk() the tree, you are actually sorting the numbers.

Walk(t.Left,ch)
ch <- t.Value
Walk(t.Right,ch)

That goes Left, current, Right. Lowest, second lowest, third lowest.

ch <- t.Value
Walk(t.Right,ch)
Walk(t.Left,ch)

This goes current, Right, Left. Second lowest, third lowest, lowest. The issue with this ordering is that the order they come out depends on the order of the tree. In the first one, the elements in the tree, and not the order, are what mattered.

What the Walk() function is really implementing is a portion of the tree sort algorithm. See: http://en.wikipedia.org/wiki/Tree_sort

Look at the source code of Tree :

// 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
}

It uses the Perm function :

> Perm returns, as a slice of n ints, a pseudo-random permutation of the
> integers [0,n).

What you see is a feature : each Tree created by New is random.