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 = 
    -- your implementation here
    (Empty, "Fail")


treeToDot : Tree Char -> String
treeToDot tree = 
    -- your implementation here
    "fail"


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         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

Solution