When two trees are equal?

Question

If in-order traversal of two binrary trees (not binary search trees) are the same, does it guarantee that the two trees are the same?

if answer is no, then what about both in-order and pre-order traversal are the same?

Answer 1

Definitely not. The two trees

  b
 / \
a   d
   / \
  c   e

and

    d
   / \
  b   e
 / \
a   c

both have an inorder traversal of a b c d e. They are, in fact, rotations, an operation which preserves inorder traversal.

Answer 2

I'm thinking "no."

It's possible for two trees to be balanced differently, but have the same "order" of node values. For instance, if, of the set

1,2,3,4,5,6,7

You build a tree:

         4
      2    6
   1   3  5   7

in-order traversal will yield 1,2,3,4,5,6,7.

however, if you choose a different root node (if the list is not sorted correctly beforehand)

           5
         4   6
       2       7   
     1   3

These two trees will give the same in-order traversal result, but are (clearly) not identical.

or even

      7
     6
    5
   4
  3
 2
1

et cetera.

This is also related to a problem with BSP (binary space partition) trees, typically used in game development collision detection and visibility determination.

The BSP stores triangles in a tree. Each node contains a triangle or facet. The left node contains all children that are "behind" the facet, while the right child contains everything that is in "front." Recurse as expected.

If you pick the left-most facet in the scene as your root, the right child will then own every other facet. If you make a bad decision for the right child, the same thing will happen. It's perfectly possible for one to build a BSP compiler that, through idiotic analysis, builds a "tree" that is actually a list (as in my last example above). The problem is to partition the data set so that each node divides the remaining list as equally as possible. This is one of the reasons that BSPs are typically generated at compile time, as building one for a very complex geometry can take hours to find the/an optimal solution.

Answer 3

NO, and its seen with this simple example

   3            2          
  2           1   3
 1           0
0  

Both have same inorder traversals [0,1,2,3]

But if inorder and preorder traversals are same then the trees are equal.