I am having trouble with the equivalent binary trees exercise on the go tour.

I've written a Walker() function to traverse the tree in node-left-right order, then used the Same() function to test two identical binary trees for equivalence.

Here is a link to my code: https://go.dev/play/p/vakNgx_CD3L

See comments in the linked go code. For some reason, with this traversal order, the equivalence tests fails when it should work. Switching the order to left-node-right or right-node-left works, though.

The print output also confuses me. This is the result when run. Why don't the first 10 numbers from traversing tree 1 match the second set of 10 numbers from traversing tree 2?

10
5
3
1
2
4
7
6
9
8
7
4
2
1
3
5
6
9
8
10
false
false

CodePudding user response：

I think the problem here is, you are using the https://pkg.go.dev/golang.org/x/tour/tree#New function which returns a random binary tree from 1k to 10k values.

The "Random" word is of importance here, so you can not expect to get same binary tree as a output from a call to tree.New(1) function.

Though the tree nodes will have values from 1 to 10 (incase of k=1) the order of the tree returned will be diffrent. You can see this clearly if you print the tree with the .String() function. Take a look at below playground code where I have printed the tree which clearly shows the returned tree will be different at each call to the tree.New function. https://go.dev/play/p/WkF8frfno17

I hope this helps :).