Can the structure of a “Complete Binary Tree”, be uniquely identified if only its pre-order or post-order or in-order traversals are given?

Question

I am unable to reason if we can construct a complete binary tree if only one of the following 3 traversals is given: pre-order, post-order, in-order.

The following is the definition of a complete binary tree:

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The above definition has been taken from this link: https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

It would be helpful if someone can prove or intuitively explain why we can or cannot uniquely construct a complete binary tree if only one of its 3 traversals is given?

Answer 1

Given $n$, there is only one shape for a complete binary tree (CBT) with $n$ nodes.

For any deterministic traversal, the correspondence between a node's position in a CBT and its position during the traversal of that CBT is completely fixed. So if a deterministic traversal is given, we can reconstruct the CBT uniquely. This applies not only to any one of pre-order, post-order, or in-order traversals, it also applies to breath-first-traversal (with the left child visited before the right child), or any other deterministic traversal as mentioned by Hendrik Jan in his comment.

Here is an example. The shape above is the only shape for a CBT with 12 nodes, which are, 1 root (at depth 0), 2 nodes at depth 1, 4 nodes at depth 2 and 5 nodes at depth 3. A pre-order traversal of that CBT visits the nodes in the following order.

1. the root node.
2. the first node of depth 1.
3. the first node of depth 2.
4. the first node of depth 3.
5. the second node of depth 3.
6. the second node of depth 2.
7. the third node of depth 3.
8. the fourth node of depth 3.
9. the second node of depth 1.
10. the third node of depth 2.
11. the fifth node of depth 3.
12. the fourth node of depth 2.

Give the list above, we know the root node is the 1^st-node visited, the first node of depth 1 is the 2^nd-node visited, ..., the fourth node of depth 3 is the 8^th-node visited and the fifth node of depth 3 is the 11^th-node visited.