11
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Since the input is guaranteed to have a specific shape (a complete binary tree), you don't really need both inputs, do you? \$\endgroup\$ – feersum Sep 26 '16 at 1:19
  • \$\begingroup\$ The binary tree is full, but not complete, so an n-element tree can have many shapes, and, in general, you do need both. \$\endgroup\$ – Lynn Sep 26 '16 at 1:23
  • \$\begingroup\$ 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) \$\endgroup\$ – Ton Hospel Sep 26 '16 at 9:51
  • \$\begingroup\$ @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] :) \$\endgroup\$ – Lynn Sep 26 '16 at 9:57
2
\$\begingroup\$

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"
\$\endgroup\$
  • \$\begingroup\$ -p adds a ; at the end, so you don't need the last ;. s;.* ;; -> s;.* ; \$\endgroup\$ – Riley Sep 26 '16 at 14:46
  • \$\begingroup\$ @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 \$\endgroup\$ – Ton Hospel Sep 26 '16 at 14:56
  • \$\begingroup\$ 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. \$\endgroup\$ – Riley Sep 26 '16 at 15:07
  • \$\begingroup\$ @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 \$\endgroup\$ – Ton Hospel Sep 26 '16 at 15:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Riley Sep 26 '16 at 15:15
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.