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)
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