<p>Well, here's the algorithm:</p>

<p>Consider the postorder traversal and replace each node with its index in the preorder traversal.</p>

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

<p>From here you can see:</p>

<ul>
<li>1 is the root because it's the last node in postorder</li>
<li>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.</li>
</ul>

<p>Consider the second problem.</p>

<p>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).</p>

<p>But note that the root of the left subtree is the item with the smallest preorder index.</p>

<p>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".</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-11-22T16:41:18.630Z
nice one..Thnx very much
rakesh
CC BY-SA 3.0
2011-11-22T23:19:50.930Z
jkff, we generally don't answer questions which are clearly off-topic, please see the [policy](http://meta.cstheory.stackexchange.com/questions/1127/deleting-answers-to-clearly-off-topic-questions-after-they-get-closed).
Kaveh
CC BY-SA 3.0
2011-11-22T14:26:24.427Z
2011-11-22T14:36:50.520Z
2011-11-22T14:36:50.520Z
jkff
<p>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.</p>

<p>If so.. could you give a rough sketch of proof otherwise could you give a counter example</p>

CC BY-SA 3.0
2011-11-22T12:29:32.383Z
Looks like a homework question. Is it?
jkff
CC BY-SA 3.0
2011-11-22T13:58:13.127Z
no.. not at all
rakesh
CC BY-SA 3.0
2011-11-22T23:17:56.877Z
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.
Kaveh
CC BY-SA 3.0
2011-11-22T23:21:13.457Z
homework or not it is not a research-level question and is therefore off-topic for cstheory.
Kaveh
CC BY-SA 3.0
2012-09-23T15:23:58.493Z
A similar question has since then been reasked and answered [on Computer Science SE](http://cs.stackexchange.com/questions/439/which-combinations-of-pre-post-and-in-order-sequentialisation-are-unique).
Gilles 'SO- stop being evil'
<co.combinatorics><ds.data-structures><tree>
unique binary tree from preorder and postorder traversals of a full binary tree
rakesh
# unique binary tree from preorder and postorder traversals of a full binary tree

(Asked by: username_0 on 2011-11-22)

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

**Tags:** co.combinatorics, ds.data-structures, tree
> **Comments:**
> **username_1**: Looks like a homework question. Is it?  
> **username_0**: no.. not at all  
> **username_2**: 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.  
> **username_2**: homework or not it is not a research-level question and is therefore off-topic for cstheory.  
> **username_3**: A similar question has since then been reasked and answered [on Computer Science SE](http://cs.stackexchange.com/questions/439/which-combinations-of-pre-post-and-in-order-sequentialisation-are-unique).  

---

## 1 answers

### Answer by username_1 on 2011-11-22. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: nice one..Thnx very much  
> **username_2**: jkff, we generally don't answer questions which are clearly off-topic, please see the [policy](http://meta.cstheory.stackexchange.com/questions/1127/deleting-answers-to-clearly-off-topic-questions-after-they-get-closed).  

---

