Tree: Height of a Binary Tree

  • + 0 comments

    Haskell

    module Main where
    
    data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
    
    inOrder :: Tree a -> [a]
    inOrder Empty = []
    inOrder (Node a left right) = inOrder left ++ [a] ++ inOrder right
    
    insertNode :: (Ord a) => Tree a -> a -> Tree a
    insertNode Empty x = Node x Empty Empty
    insertNode (Node a left right) x
        | x < a = Node a (insertNode left x) right
        | x > a = Node a left (insertNode right x)
        | otherwise = Node a left right
    
    height :: Tree a -> Int
    height Empty = 0
    height (Node _ Empty Empty) = 0
    height (Node _ left right) = 1 + max (height left) (height right)
    
    main :: IO ()
    main = do
        _ <- getLine
        xs <- fmap (map read . words) getLine :: IO [Int]
        let tree = foldl insertNode Empty xs
        print $ height tree