11

# Task

Given the pre-order and post-order traversals of a full binary tree, return its in-order traversal.

The traversals will be represented as two lists, both containing *n* distinct positive integers, each uniquely identifying a node. Your program may take these lists, and output the resulting in-order traversal, using any reasonable I/O format.

You may assume the input is valid (that is, the lists actually represent traversals of some tree).

This is code-golf, so the shortest code in bytes wins.

# Definitions

A **full binary tree** is a finite structure of **nodes**, represented here by unique positive integers.

A full binary tree is either a

leaf, consisting of a singlenode:`1`

Or a

branch, consisting of onenodewith twosubtrees(called theleftandright subtrees), each of which is, in turn, a full binary tree:`1 / \ … …`

Here’s a full example of a full binary tree:

```
6
/ \
3 4
/ \ / \
1 8 5 7
/ \
2 9
```

The **pre-order traversal** of a full binary tree is recursively defined as follows:

- The pre-order traversal of a
leafcontaining a nodenis the list [n].- The pre-order traversal of a
branchcontaining a nodenand sub-trees(L, R)is the list [n] +preorder(L) +preorder(R), where + is the list concatenation operator.

For the above tree, that’s **[6, 3, 1, 8, 2, 9, 4, 5, 7]**.

The **post-order traversal** of a full binary tree is recursively defined as follows:

- The post-order traversal of a
leafcontaining a nodenis the list [n].- The post-order traversal of a
branchcontaining a nodenand sub-trees(L, R)is the listpostorder(L) +postorder(R) + [n].

For the above tree, that’s **[1, 2, 9, 8, 3, 5, 7, 4, 6]**.

The **in-order traversal** of a full binary tree is recursively defined as follows:

- The in-order traversal of a
leafcontaining a nodenis the list [n].- The in-order traversal of a
branchcontaining a nodenand sub-trees(L, R)is the listinorder(L) + [n] +inorder(R).

For the above tree, that’s **[1, 3, 2, 8, 9, 6, 5, 4, 7]**.

In conclusion: given the pair of lists **[6, 3, 1, 8, 2, 9, 4, 5, 7]** (pre) and **[1, 2, 9, 8, 3, 5, 7, 4, 6]** (post) as input, your program should output **[1, 3, 2, 8, 9, 6, 5, 4, 7]**.

# Test cases

Each test case is in the format `preorder, postorder → expected output`

.

```
[8], [8] → [8]
[3,4,5], [4,5,3] → [4,3,5]
[1,2,9,8,3], [9,8,2,3,1] → [9,2,8,1,3]
[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7] → [11,10,12,8,2,7,4,3,5]
[1,2,3,4,5,6,7,8,9], [5,6,4,7,3,8,2,9,1] → [5,4,6,3,7,2,8,1,9]
```

Since the input is guaranteed to have a specific shape (a complete binary tree), you don't really need both inputs, do you? – feersum – 2016-09-26T01:19:57.193

The binary tree is

full, but notcomplete, so ann-element tree can have many shapes, and, in general, you do need both. – Lynn – 2016-09-26T01:23:03.513May I represent the nodes as single letters giving strings for the orders. E.g. the second example would become:

`"CDE" and "DEC" give "DCE"`

? (even using unicode letters if I need lots of nodes) – Ton Hospel – 2016-09-26T09:51:17.810@TonHospel I’d be okay with that — arguably, all you’re doing is stretching the definition of a

list of integersa little, because`"CDE"`

isn’t very different from`[67, 68, 69]`

:) – Lynn – 2016-09-26T09:57:19.823