6
\$\begingroup\$

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

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

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]]]]"
\$\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.