tour: Exercise: Equivalent Binary Trees - tree.New(1) does not create same values every time

[phluks]

Context: https://tour.golang.org/concurrency/8

Hi golang.

I'm not sure if it is on purpose or a bug, but it is quite confusing. If it is on purpose, I'd say it's not helpful.

Anyway, feel free to close the issue at your own discretion.

This code shows that calling tree.New(1) creates different trees on consecutive calls

package main

import (
    "golang.org/x/tour/tree"
    "fmt"
)

func Walker(t *tree.Tree, ch chan int) {
    if t != nil {
        ch <- t.Value
        if t.Left != nil {
            Walker(t.Left, ch)
        }
        if t.Right != nil {
            Walker(t.Right, ch)
        }
    }
}

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    Walker(t, ch)
    close(ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    fmt.Printf("Tree 1: %v\n", t1)
    fmt.Printf("Tree 2: %v\n", t2)
    c1 := make(chan int)
    c2 := make(chan int)
    go Walk(t1, c1)
    go Walk(t2, c2)

    for {
        v1, ok1 := <- c1
        v2, ok2 := <- c2
        //fmt.Printf("Values: %v, %v\n", v1, v2)
        if v1 != v2 {
            return false
        }
        if !ok1 || !ok2 {
            break
        }
    }

    return true

}

func main() {
    // force same tree
    t0 := tree.New(1)
    fmt.Printf("t0 == t0: %v\n", Same(t0, t0))
    fmt.Printf("t1 == t1: %v\n", Same(tree.New(1), tree.New(1)))
    fmt.Printf("t1 == t2: %v\n", Same(tree.New(1), tree.New(2)))
}

// outputs
Tree 1: ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10)
Tree 2: ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10)
t0 == t0: true
Tree 1: ((((1) 2 (3)) 4 (5 (6))) 7 ((8) 9 (10)))
Tree 2: ((((((1) 2) 3 (4)) 5 (6)) 7) 8 ((9) 10))
t1 == t1: false
Tree 1: ((1 ((((2) 3 (4)) 5) 6)) 7 ((8) 9 (10)))
Tree 2: ((2) 4 ((((6 (8)) 10 ((12) 14)) 16) 18 (20)))
t1 == t2: false

[zhujinhe]

The Walker need to use Inorder traversal (Left, Root, Right) to generate 1, 2, 3, ... 10.

func Walker(t *tree.Tree, ch chan int) {
    if t != nil {
        if t.Left != nil {
            Walker(t.Left, ch)
        }
        ch <- t.Value
        if t.Right != nil {
            Walker(t.Right, ch)
        }
    }
}

[0xDEAD]

This code shows that calling tree.New(1) creates different trees on consecutive calls

Isn't that the idea of the example? All created trees contain the same values but they are balanced differently. A pure "deep equal test" (that you can easily implement in a synchronous manner) will not suffice, but you need to walk the trees in parallel.