CODEWITHSUNDEEP
data-structurestreetraversal
Lily
Lily

Reputation: 6022

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?

Upvotes: 5

Views: 3389

Answers (5)

Kishan Stud
Kishan Stud

Reputation: 1

One thing you can do is use level order 5 4 6 2 7
1 3

lvel order- 5 4 6 2 N N 7 1 3 N N N N N N

Upvotes: 0

Abhishek Singh
Abhishek Singh

Reputation: 953

Inorder and any one of pre-order or post-order, uniquely define a tree structure. Nothing less.

Upvotes: 1

theReverseFlick
theReverseFlick

Reputation: 6044

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.

Upvotes: 2

3Dave
3Dave

Reputation: 29051

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.

Upvotes: 1

Josh Lee
Josh Lee

Reputation: 177584

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.

Upvotes: 9

Related Questions