# Tree traversing

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

• Are the elements guaranteed to be distinct? – Peter Taylor Oct 3 '15 at 21:16
• So in the result, if there's only a single child, it's not defined whether the child is the left or the right? – Johannes Schaub - litb Oct 4 '15 at 9:36

[a]#_=show a

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