CODEWITHSUNDEEP
go
Jun Jie
Jun Jie

Reputation: 21

Golang tree traversal order

Just started trying out golang, stuck at trying to figure out tree traversal exercise in the tutorial

I can't figure out how the different order of tree traversal affects the result of the golang tutorial on equivalent tree (https://tour.golang.org/concurrency/8)

Specifically... how is this...

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

different from this...

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

    if t.Left != nil{
        Walk(t.Left, ch)
    }
    ch<-t.Value
    if t.Right != nil{
        Walk(t.Right, ch)
    }
}

I would have thought both would provide the same result with the following function:

func Same(t1, t2 *tree.Tree) bool{
    chTree1 := make(chan int)
    chTree2 := make(chan int)

    go Walk(t1, chTree1)
    go Walk(t2, chTree2)

    for i:= 0; i < 10; i++{
        a, b := <-chTree1, <-chTree2
        //fmt.Printf("a: %v, b: %v\n", a, b)

        if a != b {
            return false
        }
    }
    return true
}

Upvotes: 2

Views: 2067

Answers (1)

abhink
abhink

Reputation: 9126

This is happening because of the way New is implemented:

func New func New(k int) *Tree

New returns a new, random binary tree holding the values k, 2k, ..., 10k.

Thus, while two trees created using tree.New(1) will have a different structure, they'll have the exact same elements.

Your second Walk implementation (below):

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

    if t.Left != nil{
        Walk(t.Left, ch)
    }
    ch<-t.Value
    if t.Right != nil{
        Walk(t.Right, ch)
    }
}

is performing an inorder traversal of the tree. An inorder traversal always returns the elements of the trees in a sorted order.

Hence, any call to this Walk with same value of k to tree.New(k) will result in the same list of elements, namely k, 2k, ..., 10k.

This results in this version of Walk always returning true.

Upvotes: 2

Related Questions