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 single node:
1
Or a branch, consisting of one node with two subtrees (called the left and right 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 leaf containing a node n is the list [n].
- The pre-order traversal of a branch containing a node n and 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 leaf containing a node n is the list [n].
- The post-order traversal of a branch containing a node n and sub-trees (L, R) is the list postorder(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 leaf containing a node n is the list [n].
- The in-order traversal of a branch containing a node n and sub-trees (L, R) is the list inorder(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]
"CDE" and "DEC" give "DCE"
? (even using unicode letters if I need lots of nodes) \$\endgroup\$"CDE"
isn’t very different from[67, 68, 69]
:) \$\endgroup\$