为什么在“遍历：等效二叉树”中将遍历从“有序”更改为“前/后”才能使答案错误？

Question

In the concurrency section of Golang tour there is an exercise as follows. The problem statement wants to verify that two input trees are as the same or not.

The problem here is when we changing the traversal order from in-order to pre/post-order it fails. i.e the bellow code works correctly

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

but if we first put the value to channel and then went to node's children its answer became wrong(run this and this for same input which output is difference).

Since we used the same code for traversing its expected that the order should not matter(i.e values goes to the channel in the same order...).

PS: You can find more answers to this exercise here.

Answer 1

The answer for this one is rather related to data structures rather than Golang syntax and has to do with Binary Search Tree properties.

As the documentation states tree.New func returns a random constructed key:

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

An inorder traversal promises the output to be sorted, but it isn't the case for preorder and postorder traversal and therefore the output would not be equal for these traversals.

Consider the following tree:

       4
      / \
     2   5
    / \
   1   3

InOrder traverse: 1, 2, 3, 4, 5

PostOrder traverse: 1 3 2 5 4

For more information: Binary Trees