### Problem 69: Dotstring representation of binary trees.

The first part of the problem is straightforward preorder traversal:

```
tree2ds :: Tree Char -> String
tree2ds Empty = "."
tree2ds (Branch v l r) = v : tree2ds l ++ tree2ds r
```

For the second part, constructing a tree from a preorder sequence is unambiguous. Why?
Didn’t problem 68 ask us to construct a tree with *the same preorder sequence* as the
given, and why didn’t it state clearly to construct *the same tree*? As an exercise, prove
that the dotstring representation can help us construct *the same tree*, a stricter
problem statement than “all trees with the same preorder sequence”.

```
ds2tree :: String -> (Tree Char, String)
ds2tree "" = (Empty, "")
ds2tree ( c : cs )
| c == '.' = (Empty, cs)
| otherwise = (Branch c l r, rrest)
where (l, lrest) = ds2tree cs
(r, rrest) = ds2tree lrest
```

### Problem 70: Count the nodes of a multiway tree.

Oooh, multiway trees, neat!

```
nnodes :: Tree a -> Int
nnodes (Node _ ts) = 1 + sum ( map nnodes ts )
```

and to construct a multiway tree from a node string, & vice versa:

```
tree_to_string :: Tree Char -> String
tree_to_string (Node v ts) = v : concatMap tree_to_string ts ++ "^"
-- Little helper to grab a range [m, n) from a sequence:
take_range str m n = take (n - m) $ drop m str
string_to_tree :: String -> Tree Char
string_to_tree ( c : '^' : cs) = Node c []
string_to_tree ( c : cs) = Node c ns
where
-- The indices in `levels` where zeroes appear:
zeroes = map fst $ filter ((==) 0 . snd) $ zip [0,1..] levels
-- `levels` is numbering the level we're on after 'processing' each node
-- in the string, with -1 signifying the end (above the root):
levels = scanl (+) 0 $ map (\v -> if v == '^' then -1 else 1) cs
-- Think of `ns` as leaves we need to hang:
ns = map (string_to_tree . uncurry (take_range cs)) $ zip (init zeroes) (tail zeroes)
```

### Problem 71: Determine the internal path length of a tree.

Not too hard, after all:

```
ipl :: Tree a -> Int
ipl = ipl' 0
where ipl' d (Node _ ts) = d + sum ( map (ipl' (d+1) ) ts)
```

### Problem 72: Construct the bottom-up order sequence of the tree nodes.

Problem description looks like a DFS where children nodes are grouped, so that’s exactly what we’ll do:

```
bottom_up :: Tree a -> [a]
bottom_up (Node v ts) = concatMap bottom_up ts ++ [v]
```

We’ll leave problem 73 for the next time. Cheerio!

« Past Future »