1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If you know the number of nodes, then you know the structure (form) of the complete binary tree. Then, starting with any decent order, you can move the elements to their position in the tree. $\endgroup$ – Hendrik Jan Jun 3 at 18:35
  • $\begingroup$ @HendrikJan Thanks! Now I get it! $\endgroup$ – Aditya S Jun 4 at 4:18
2
$\begingroup$

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.

A complete binary tree with 12 nodes 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 1st-node visited, the first node of depth 1 is the 2nd-node visited, ..., the fourth node of depth 3 is the 8th-node visited and the fifth node of depth 3 is the 11th-node visited.

| cite | improve this answer | |
$\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.