https://www.futurelearn.com/courses/functional-programming-haskell/1/steps/116718

binarytree.hs

--import Control.Monad.Error

data Tree = Leaf | Node Int Tree Tree deriving Show

getSortedTreeExample = Node 5 (Node 2 Leaf (Node 4 Leaf Leaf)) (Node 13 (Node 8 Leaf (Node 11 Leaf Leaf)) Leaf)
getTreeExample = Node 5 (Node 2 Leaf (Node 4 Leaf Leaf)) (Node 13 (Node 8 (Node 11 Leaf Leaf) Leaf) Leaf)

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

treeSum :: Tree -> Int
treeSum Leaf = 0
treeSum (Node x leftSubtree rightSubtree) = 
  x + (treeSum leftSubtree) + (treeSum rightSubtree)

addNewMax :: Tree -> Tree
-- add a new max element to tree
addNewMax Leaf = Node 0 Leaf Leaf  -- input tree with no nodes
addNewMax (Node x t1 Leaf) = Node x t1 (Node (x+1) Leaf Leaf)  -- this is the rightmost Node
addNewMax (Node x t1 t2) = Node x t1 (addNewMax t2) -- intermediate node, go down right subtree

--addNewMax :: Tree -> Either (String Tree)
-- add a new max element to tree
--addNewMax Leaf = Either Right (Node 0 Leaf Leaf)  -- input tree with no nodes
--addNewMax (Node x t1 Leaf) = Either Right (Node x t1 (Node (x+1) Leaf Leaf))  -- this is the rightmost Node
--addNewMax (Node x t1 t2) = 
--  do 
--     --t2' <- addNewMax t2
--     (Node 1 Leaf Leaf)--Error Right (Node x t1 t2') -- intermediate node, go down right subtree

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

insertNew :: Tree -> Int -> Tree
insertNew Leaf x = Node x Leaf Leaf
insertNew (Node v leftSubtree rightSubtree) x 
  | x == v = (Node v leftSubtree rightSubtree)
  | x > v = Node v leftSubtree (insertNew rightSubtree x)
  | x < v = Node v (insertNew leftSubtree x) rightSubtree

toList :: Tree -> [Int]
toList Leaf = []
toList (Node x left right) = (toList left) ++ [x] ++ (toList right)

-- There's an idiomatic way to turn a tree into a list by using a traversal with an accumulator argument:
--traverse init (Node l r) = traverse (traverse init r) l
--traverse init (Leaf x)   = x : init

--cc tree = traverse [] (fmap2 h tree)