Is this a total ordering of the set of full labelled binary trees?

83 Views Asked by At

Consider a binary tree labelled by some ordered set of letters. Traversing the tree in preorder determines a sequence of letters - a word.

A binary tree is called full if all its non-leaf vertices have exactly two children.

Given two such binary trees that are also full, and determine the same word, does it follow that the two trees are equal?

1

There are 1 best solutions below

0
On BEST ANSWER

There will definitely be more than one full binary tree that will yield a particular pre-order traversal. So short answer to your question will be no.

Here is a sketch for a potential counter-example. Consider the following 2 trees.

enter image description here

enter image description here

There will exist an assignment of letters such that the pre-order traversal on both the above trees yields the same word. However, the trees are clearly dissimilar, and hence your claim is false.