Functional Programming in Haskell - The University of Glasgow

trees.hs

data Tree =
      Leaf
    | Node Int Tree Tree
    deriving Show

treeDepth :: Tree -> Int
treeDepth Leaf = 0
treeDepth (Node _ a b) = 1 + max (treeDepth a) (treeDepth b)

treeSum :: Tree -> Int
treeSum Leaf = 0
treeSum (Node n a b) = n + treeSum a + treeSum b

isSortedTree :: Tree -> Int -> Int -> Bool
isSortedTree Leaf _ _ = True
isSortedTree (Node x leftSubtree rightSubtree) minVal maxVal =
  let leftSorted  = isSortedTree leftSubtree  minVal x
      rightSorted = isSortedTree rightSubtree x      maxVal
   in x >= minVal && x < maxVal && leftSorted && rightSorted

-- isSortedTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) minBound maxBound

addNewMax :: Tree -> Tree
addNewMax Leaf = Node 0 Leaf Leaf
addNewMax (Node x t1 Leaf) = Node x t1 (Node (x+1) Leaf Leaf)
addNewMax (Node x t1 t2) = Node x t1 (addNewMax t2)

treeToList :: Tree -> [Int]
treeToList Leaf = []
treeToList (Node value leftSubtree rightSubtree) =
  mconcat [treeToList leftSubtree, [value], treeToList rightSubtree]