99 questions/Solutions/68
Preorder and inorder sequences of binary trees. We consider binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67.
a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence of the example in problem P67.
b) Can you use preorder/2 from problem part a) in the reverse direction; i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.
c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.
treeToPreorder :: Tree Char -> String
treeToPreorder = preorder
where preorder Empty = ""
preorder (Branch x l r) = x : preorder l ++ preorder r
treeToInorder :: Tree Char -> String
treeToInorder = inorder
where inorder Empty = ""
inorder (Branch x l r) = inorder l ++ x : inorder r
-- Given a preorder string produce a binary tree such that its preorder string
-- is identical to the given one.
preToTree :: String -> Tree Char
preToTree "" = Empty
preToTree (c:cs) = Branch c Empty (preorderToTree cs)
-- Given a preorder and an inorder string with unique node chars produce the
-- corresponding binary tree.
preInTree :: Monad m => String -> String -> m (Tree Char)
preInTree [] [] = return Empty
preInTree po@(x:xs) io = do (lio,_:rio) <- return $ break (== x) io
(lpo,rpo) <- return $ splitAt (length lio) xs
l <- preInTree lpo lio
r <- preInTree rpo rio
return $ Branch x l r
preInTree _ _ = fail "woops"