Pre-order + post-order to in-order

Question

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]

Answer 1

Perl, 69 66 62 56 53 bytes

Includes +1 for -p

Takes postorder followed by preorder as one line separated by space on STDIN (notice the order of pre and post). Nodes are represented as unique letters (any character that is not space or newline is OK).

inpost.pl <<< "98231 12983"

inpost.pl:

#!/usr/bin/perl -p
s%(.)(.)+\K(.)(.+)\3(\1.*)\2%$4$5$3$2%&&redo;s;.+ ;;

Using the original purely numeric format needs a lot more care to exactly identify a single number and comes in at 73 bytes

#!/usr/bin/perl -p
s%\b(\d+)(,\d+)+\K,(\d+\b)(.+)\b\3,(\1\b.*)\2\b%$4$5,$3$2%&&redo;s;.+ ;;

Use as

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"

Answer 2

Haskell, 84 83 bytes

(a:b:c)#z|i<-1+length(fst$span(/=b)z),h<- \f->f i(b:c)#f i z=h take++a:h drop
a#_=a

Answer 3

JavaScript (ES6), 100 bytes

f=(s,t,l=t.search(s[1]))=>s[1]?f(s.slice(1,++l+1),t.slice(0,l))+s[0]+f(s.slice(l+1),t.slice(l)):s[0]

I/O is in strings of "safe" characters (e.g. letters or digits). Alternative approach, also 100 bytes:

f=(s,t,a=0,b=0,c=s.length-1,l=t.search(s[a+1])-b)=>c?f(s,t,a+1,b,l)+s[a]+f(s,t,l+2+a,l+1,c-l-2):s[a]

Answer 4

APL (Dyalog Extended), 31 bytes

{0::⍵⋄∊2⌽∇¨⍵⊂⍨¯⍸1 2,2⊃⍋⍵}⍤⌽⍤⍳⊇⊣

Try it online!

An anonymous infix function that takes the preorder on its left and the postorder on its right.

How it works

This solution uses multiple APL-specific features.

Given the input [7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7], it first computes the index of (⍳) each number in the right arg inside the left arg. The index is 1-based by default. This allows to work on a single array instead of two arrays. We will manipulate the array of "indices" until the very end.

      pre←7 8 10 11 12 2 3 4 5 ⋄ post←11 12 10 2 8 4 5 3 7
      pre ⍳ post
4 5 3 6 2 8 9 7 1

Then take the reverse ⌽:

      ⌽4 5 3 6 2 8 9 7 1
1 7 9 8 2 6 3 5 4

At this point, we can identify the root and left and right branches: 1 is the root, 7 9 8 (after 1 and before 2) are on the right branch, and 2 6 3 5 4 are on the left branch. Each branch can be handled recursively (where the first element is the root of the branch, and that +1 splits the left and right branches). So we create a recursive inline function {...} where ⍵ denotes the argument and ∇ is the recursive call.

Inside it, we will eventually split the array 1 7 9 8 2 6 3 5 4 to 3 subarrays (1)(7 9 8)(2 6 3 5 4). We can use "partition" ⊂, which splits the array at ones as the starting point, so giving 1 1 0 0 1 0 0 0 0 will do.

      1 1 0 0 1 0 0 0 0⊂1 7 9 8 2 6 3 5 4
┌─┬─────┬─────────┐
│1│7 9 8│2 6 3 5 4│
└─┴─────┴─────────┘

2⊃⍋⍵ is a short way to extract the index of the second smallest element. ⍋ is called "grade up", which is related to sorting but doesn't sort the elements directly; instead, it tells us which element should go where in the sorted array. So the result looks like [index of the smallest, index of the 2nd smallest, ..., index of the largest]. Naturally, taking the second element from that gives index of the 2nd smallest.

      {2⊃⍋⍵}1 7 9 8 2 6 3 5 4
5

It gives the position of the third 1 in the partition marker. The first and second are trivial (1 and 2). So we concatenate (,) the 5 with 1 2, and convert it to the counts (¯⍸) giving [count of 1s, count of 2s, ...]:

      {¯⍸1 2,2⊃⍋⍵}1 7 9 8 2 6 3 5 4
1 1 0 0 1

⊂ in Extended accepts short markers, so we can use the above to partition ⍵:

      {⍵⊂⍨¯⍸1 2,2⊃⍋⍵}1 7 9 8 2 6 3 5 4
┌─┬─────┬─────────┐
│1│7 9 8│2 6 3 5 4│
└─┴─────┴─────────┘

Now it's time for recursive call. 2⊃⍋⍵ on a single-element array will error, so we guard it with 0::⍵ (catch any error and return the argument as-is). On the result, the left branch should be on the left of the root, so we rotate the result twice to the left 2⌽, and flatten it ∊.

      {0::⍵⋄∊2⌽∇¨⍵⊂⍨¯⍸1 2,2⊃⍋⍵} 1 7 9 8 2 6 3 5 4
4 3 5 2 6 1 8 7 9

Finally, we convert each of the "indices" to the number at that index in the preorder (the left arg).

      4 3 5 2 6 1 8 7 9 ⊇ pre
11 10 12 8 2 7 4 3 5

---

For comparison, porting the Haskell answer is quite longer:

APL (Dyalog Extended), 42 bytes

{0::⍺⋄l←⍵⍳2⊃⍺⋄(⍵∇⍨l↑1↓⍺),(⊃⍺),(l↓1↓⍺)∇l↓⍵}

Try it online!

Answer 5

Python 3.8 (pre-release), 85 bytes

f=lambda a,b:a==b and a or f(a[1:(i:=a.find(b[-2]))],b[:i-1])+a[0]+f(a[i:],b[i-1:-1])

Try it online!

Input is 2 strings, each string can contain any character.

Explanation:

Consider the input:

Preorder  631829457
Postorder 129835746

We can split each input into 3 parts (the root, the left subtree, and right subtree) as follows:

• The first character in the preorder traversal must be the root. Similarly, the last character in the postorder traversal must also be the root.
• Since 4 is the second-to-last character in the postorder string, we know that 4 must be the root of the right subtree. This means that 4 must be the first character in the preorder string of the right subtree.

Preorder  6 | 31829 | 457
Postorder     12983 | 574 | 6

We can then recurs on the left and right part.