If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T.

If so.. could you give a rough sketch of proof otherwise could you give a counter example

  • 3
    $\begingroup$ Looks like a homework question. Is it? $\endgroup$ – jkff Nov 22 '11 at 12:29
  • $\begingroup$ no.. not at all $\endgroup$ – rakesh Nov 22 '11 at 13:58
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Nov 22 '11 at 23:17
  • $\begingroup$ homework or not it is not a research-level question and is therefore off-topic for cstheory. $\endgroup$ – Kaveh Nov 22 '11 at 23:21
  • 1
    $\begingroup$ A similar question has since then been reasked and answered on Computer Science SE. $\endgroup$ – Gilles 'SO- stop being evil' Sep 23 '12 at 15:23

Well, here's the algorithm:

Consider the postorder traversal and replace each node with its index in the preorder traversal.

For example, let's say you get: 3 4 2 7 8 6 9 5 1.

From here you can see:

  • 1 is the root because it's the last node in postorder
  • It only remains to split "3 4 2 7 8 6 9 5" (without the 1) into two parts: left and right subtree, and then recursively process them.

Consider the second problem.

Note that this set is of the form: (all nodes of left subtree in some order) (all nodes of right subtree in some order) - i.e. the subtree ranges don't intersect. So we only have to find the boundary, which, given it's postorder traversal, should be the root of the left subtree (it's the last thing processed from the left subtree; all that follows is the right subtree).

But note that the root of the left subtree is the item with the smallest preorder index.

So this means that in "3 4 2 7 8 6 9 5", the left subtree is rooted at 2, and the problem splits into "3 4 2" and "7 8 6 9 5".

Recursively, we get a tree: 1 { left = 2 { left = 3, right = 4}, right = 5 {left = 6 {left = 7, right = 8}, right = 9}}.

P.S. Note that in this form the algorithm is O(n log n), but it's easy to make it O(n) - just remember in a lookup table (obviously in O(n)) for each element "x" of the array, the position of x+1 - then, whenever you pick x as a root, the left subtree ends at the position of x+1.

| cite | improve this answer | |
  • $\begingroup$ nice one..Thnx very much $\endgroup$ – rakesh Nov 22 '11 at 16:41
  • $\begingroup$ jkff, we generally don't answer questions which are clearly off-topic, please see the policy. $\endgroup$ – Kaveh Nov 22 '11 at 23:19

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