# Problem 69

Using the preorder sequence of values and dots (.) to represent empty subtrees we can unambiguously represent a binary tree.

a) Write a function to create the dot-string representation of a tree.

b) Write a function to build a tree from a dot-string.

## Example

``````tree69 = "abd..e..c.fg..."
tree69 == treeToDot <| dotToTree tree69
``````

## Unit Test

``````import Html
import List
import Maybe
import String

type Tree a
= Empty
| Node a (Tree a) (Tree a)

dotToTree : String -> (Tree Char, String)
dotToTree s =
(Empty, "Fail")

treeToDot : Tree Char -> String
treeToDot tree =
"fail"

main =
Html.text
(if (test) then
else
"Your implementation failed at least one test."
)

test : Bool
test =
List.all ((==) True)
[ tree67 == Tuple.first (dotToTree dot67)
, dot67 == treeToDot tree67
, tree69a == Tuple.first (dotToTree dot69a)
, dot69a == treeToDot tree69a
, tree69b == Tuple.first (dotToTree dot69b)
, dot69b == treeToDot tree69b
]

dot67 = "abd..e..c.fg..."

tree67 =
Node 'a'
(Node 'b'
(Node 'd' Empty Empty)
(Node 'e' Empty Empty))
(Node 'c'
Empty
(Node 'f'
(Node 'g' Empty Empty)
Empty))

dot69a = "123..4..5.67.89...."

tree69a =
Node '1'
(Node '2'
(Node '3' Empty Empty)
(Node '4' Empty Empty))
(Node '5'
Empty
(Node '6'
(Node '7'
Empty
(Node '8'
(Node '9' Empty Empty)
Empty))
Empty))

dot69b = "621..43..5..7.."

tree69b =
Node '6'
(Node '2'
(Node '1' Empty Empty)
(Node '4'
(Node '3' Empty Empty)
(Node '5' Empty Empty)))
(Node '7' Empty Empty)
``````

## Hints

1. `String.uncons` and `String.fromChar` may come in handy.
2. To convert from string to tree recurse in preorder with a function that returns two values, the tree value and the unused portion of the string.

Solution