11
$\begingroup$

This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.

It is also mentioned that the in-order traversal of two different trees can be the same though they are structurally different. Is there an example of this?

$\endgroup$
28
$\begingroup$

Tree Examples (image):

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3   

This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.

Tree B root׳s value is 1, having a left child with value 2 and a right child with value 3.

In both cases the Preorder traversal is 1->2->3.

$\endgroup$
  • 11
    $\begingroup$ This is actually a specific case of a general rule that for any tree of some order, there is a linear tree of only left (or only right) children that has the same order. $\endgroup$ – Dancrumb Jun 16 at 14:55
  • 5
    $\begingroup$ @Dancrumb Which in turn is a specific case of a general rule that for any tree with N nodes, and for any tree shape (=unlabeled tree) with N nodes, there is a way of labeling the latter so that it shares the traversal with the former. This holds for any traversal (pre-/post-/in-order visit). $\endgroup$ – chi Jun 16 at 19:20
8
$\begingroup$

Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $1,2,\dots,n$.

This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another given tree.

This will not work if we have to assume other properties of the tree. For instance, if the tree is supposed to be a binary search tree, with all keys different, its pre-order sequence will uniquely determine the tree.

$\endgroup$
8
$\begingroup$

Counting argument

The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes,

    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

Labeling these gives a factor of $n!$ on top of that, so that the number of labeled binary trees is $$\frac{(2n)!}{(n+1)!} = 2n\cdot(2n-1)\cdot \dots (n+2).$$

By contrast there are only $n!$ traversals of a tree of $n$ nodes. Since we just multiplied the former by $n!$, no traversal can therefore contain the full structure of the tree for $C_n>1$ hence $n>1.$ And this in general holds for any data structure which has more than one configuration with unlabeled nodes; you don't need to know this detail about the Catalan numbers at all, as long as you know that there are at least two unlabeled binary trees of size $n$.

$\endgroup$
1
$\begingroup$

Regarding your second question, yes two structurally different trees can have same inorder traversal. One such example is:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

Inorder traversal of both the trees is same. 2 -> 1 -> 3

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.