Search code examples
data-structurestreetraversal

When two trees are equal?

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?

Solution

  • 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.