14
\$\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\$
4
  • \$\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, 2016 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, 2016 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, 2016 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, 2016 at 9:57

5 Answers 5

5
\$\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\$
5
  • \$\begingroup\$ -p adds a ; at the end, so you don't need the last ;. s;.* ;; -> s;.* ; \$\endgroup\$
    – Riley
    Sep 26, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 15:15
4
\$\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\$
2
+200
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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