CODEWITHSUNDEEP
goconcurrency
Bonje Fir
Bonje Fir

Reputation: 840

Why changing the traversal from In-order to Pre/Post-order makes the answer wrong in "Exercise: Equivalent Binary Trees"?

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.

Upvotes: 0

Views: 169

Answers (1)

Shmulik Klein
Shmulik Klein

Reputation: 3914

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

Upvotes: 1

Related Questions