Solution for #FLhaskell course 3.9

sortedtree.hs

-- sortedtree.hs
-- Jeremy.Singer@glasgow.ac.uk
-- Example code for #FLhaskell course
-- Nodes contain integers, Leaves are empty
data Tree
    = Leaf
    | Node Int
           Tree
           Tree
    deriving (Show)

treeDepth :: Tree -> Int
-- longest path from root to a leaf
treeDepth Leaf = 0
treeDepth (Node _ leftSubtree rightSubtree) =
    1 + max (treeDepth leftSubtree) (treeDepth rightSubtree)

treeSum :: Tree -> Int
-- adds upp all the values in the tree nodes
treeSum Leaf = 0
treeSum (Node x leftSubtree rightSubtree) =
    x + (treeSum leftSubtree) + (treeSum rightSubtree)

isSortedTree :: Tree -> Int -> Int -> Bool
-- is the tree sorted in-order?
-- the two Int params indicate min and max
-- for the current subtree
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

addNewMax :: Tree -> Tree
-- add a new max element to tree
-- will go down rightmost path to Leaf
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

insertInOrd :: Int -> Tree -> Tree
-- insert a value in the tress in order
insertInOrd x Leaf = Node x Leaf Leaf
insertInOrd x (Node x' leftSubtree rightSubtree)
    | x < x' = Node x' (insertInOrd x leftSubtree) rightSubtree
    | x == x' = Node x leftSubtree (Node x Leaf rightSubtree)
    | x > x' = Node x' leftSubtree (insertInOrd x rightSubtree)

treeToList :: Tree -> [Int]
-- convert from a Tree into a List
treeToList Leaf = []
treeToList (Node x leftSubtree rightSubtree) =
    (treeToList leftSubtree) ++ [x] ++ (treeToList rightSubtree)