10
$\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?

Improve this question
$\endgroup$
2

5 Answers 5

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Jun 16, 2019 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
    Commented Jun 16, 2019 at 19:20
10
$\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$.

Improve this answer
$\endgroup$
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.

Improve this answer
$\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

Improve this answer
$\endgroup$
0
$\begingroup$

Given a preorder traversal of a tree, say a-b-c-d-e-f, you can guess a tree as follows:

  • use the first element as the root,

  • partition the rest of the sequence in a number of subsequences than will correspond to descendants, left to right,

  • repeat recursively.

E.g.

 abcdefg

    a
  / | \
bc def g

     a
  /  |  \
 b   d   g
 |  / \
 c  e f

It should be clear that on every subdivision levels, there are several choices.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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