Tree traversing

Question

Have you heard about trees?

When performing DFS on a binary tree, you can traverse it in 3 possible orders.

• Root, left node, right node (Pre-order)
• Left node, Root, right node (In-order)
• Left node, right node, root (Post-order)

Check wikipedia to know more.

For this challenge, you have to provide a program that, given the pre and in order traverses of a tree returns the original tree.

Example 1:

Inputs Preorder:

[1 2 3 4 5 6 7]

In order:

[2 1 4 3 6 5 7]

Returns:

[1 [2 3 [4 5 [6 7]]]]

NOTES:

Result notation

[a [b c]]

Node a is the parent of nodes b and c. However in this one

[a [b [c]]]

Node a is the parent of node b, but it's b in this case the parent of c.

More considerations

• The tree might not be balanced.
• For every 2 traverses, the original tree is unique.
• Submissions can be programs and functions.
• The input format has to be a sequence of numbers representing the order in which the nodes are visited.
• The output format must be exactly as specified above.
• Shortest code in bytes wins.

Good luck

• Peter Taylor: Are the elements guaranteed to be distinct?
• Johannes Schaub - litb: So in the result, if there's only a single child, it's not defined whether the child is the left or the right?

Answer 1

Haskell, 114 bytes

[a]#_=show a
(a:b)#c|(d,_:e)<-span(/=a)c,(f,g)<-splitAt(length d)b=[a]#c++" ["++f#d++' ':g#e++"]"
a?b='[':a#b++"]"

Example run:

*Main> [1,2,3,4,5,6,7]?[2,1,4,3,6,5,7]
"[1 [2 3 [4 5 [6 7]]]]"