Pre-order + post-order to in-order

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 , 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]

Lynn

Posted 2016-09-25T23:37:53.903

Reputation: 55 648

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 not complete, so an n-element tree can have many shapes, and, in general, you do need both. – Lynn – 2016-09-26T01:23:03.513

May 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 integers a little, because "CDE" isn’t very different from [67, 68, 69] :) – Lynn – 2016-09-26T09:57:19.823

Answers

2

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"

Ton Hospel

Posted 2016-09-25T23:37:53.903

Reputation: 14 114

-p adds a ; at the end, so you don't need the last ;. s;.* ;; -> s;.* ; – Riley – 2016-09-26T14:46:52.480

@Riley I know. That's why I have the ; at the end. But -p actually adds \n; to the end in a -e program. In a file it adds just ; if and only if the file does not end on \n. Since I want to claim -p as +1 and not +3 the program needs to work from the commandline, so with -e. And I don't want the spurious newline in the output I would then get – Ton Hospel – 2016-09-26T14:56:59.560

If you run it on the commandline don't you need ' around it? If you run it the way you have it (call a file with <<<) you can leave the last ; off. – Riley – 2016-09-26T15:07:54.880

@Riley It depends on the interpretation of the scoring method for perl. I usually submit my code as a file since I think that is less ephemeral. But if you look at my submissions you will see that if the code *must* be in a file (because e.g. it has ' or uses do$0 etc.) I always score -p as +3 (space,minus,p), but if the code would also work on the commandline where you get the -e and the ' for free I score it as +1 since it can be bundled with the e – Ton Hospel – 2016-09-26T15:13:08.947

Okay, I just wasn't clear on exactly how command line submissions score. I didn't realize you get ' for free. Thanks for clearing that up. – Riley – 2016-09-26T15:15:55.777

3

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

dianne

Posted 2016-09-25T23:37:53.903

Reputation: 1 049

2

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]

Neil

Posted 2016-09-25T23:37:53.903

Reputation: 95 035