Can we construct a full binary tree with only postorder traversal or preorder traversal?

Question

For example, we are provided with only post order traversal array or only pre order traversal array. Can we reconstruct the binary tree back? If we know that the binary tree is full. Moreover, if it is not, is it possible to construct the full binary if know both preorder and post order at the same time?

Accepted Answer

No, you can't from one list alone.

think of the postorder list: `4 5 2 3 1`

```
    1         1   
   / \       / \
  2   3     4   3
 / \           / \
4   5         5   2
```

both trees are possible, but we don't know which one generated the list

Assuming every element in the tree is unique, we know that preorder is build like that:

```
[Node][     LeftTree     ][     RightTree     ]
```

and postorder like this:

```
[     LeftTree     ][     RightTree     ][Node]
```

if we have two lists, preorder `1 2 4 5 3` and postorder `4 5 2 3 1`, we know that `1` is the root of the tree, because it is the first number of the preorder list (and the last number of the postorder list). Furthermore we know that `2` must be the root of the left tree and `3` the root of the right tree, because they are the first numbers after the root node which are roots of the left or right tree. With this in mind we can split the lists into this:

```
           [Root in preorder] [ LeftTree ] [RightTree] [Root in postorder]
preorder:        [1]             [2 4 5]      [3]     
postorder:                       [4 5 2]      [3]              [1]   
```

From here you can do this algorithm recursively with the left and right tree and in the end you get this:

```
    1     
   / \      
  2   3    
 / \       
4   5
```

Since every element is unique there is only one way to build the tree and therefore you can rebuild a tree from its postorder and preorder list.

In case you have elements that are the same you can't build a unique tree, example:

```
preorder:  1 X X 5 X
postorder: X 5 X X 1
```

from these lists you could create these two trees:

```
    1         1   
   / \       / \
  X   X     X   X
 / \           / \
X   5         5   X
```

Can we construct a full binary tree with only postorder traversal or preorder traversal?

Solution

Problem

Related problems