AVL Tree Implementation

data AVLTree a = Empty | Node a Int (AVLTree a) (AVLTree a)
    deriving (Show, Eq)

-- Get height of a tree
height :: AVLTree a -> Int
height Empty = 0
height (Node _ h _ _) = h

-- Calculate balance factor
balanceFactor :: AVLTree a -> Int
balanceFactor Empty = 0
balanceFactor (Node _ _ left right) = height left - height right

-- Create a new node with correct height
makeNode :: a -> AVLTree a -> AVLTree a -> AVLTree a
makeNode val left right = Node val newHeight left right
  where
    newHeight = 1 + max (height left) (height right)

-- Right rotation
rotateRight :: AVLTree a -> AVLTree a
rotateRight (Node y _ (Node x _ a b) c) = makeNode x (makeNode y b c) a
rotateRight tree = tree

-- Left rotation
rotateLeft :: AVLTree a -> AVLTree a
rotateLeft (Node x _ a (Node y _ b c)) = makeNode y a (makeNode x b c)
rotateLeft tree = tree

-- Insert with balancing
insert :: (Ord a) => a -> AVLTree a -> AVLTree a
insert val Empty = makeNode val Empty Empty
insert val (Node nodeVal _ left right)
    | val < nodeVal = balance $ makeNode nodeVal (insert val left) right
    | val > nodeVal = balance $ makeNode nodeVal left (insert val right)
    | otherwise = Node nodeVal (height (Node nodeVal 0 left right)) left right

-- Balance the tree
balance :: AVLTree a -> AVLTree a
balance tree@(Node val _ left right)
    | bf > 1 && balanceFactor left >= 0 = rotateRight tree
    | bf > 1 && balanceFactor left < 0 = rotateRight $ makeNode val (rotateLeft left) right
    | bf < -1 && balanceFactor right <= 0 = rotateLeft tree
    | bf < -1 && balanceFactor right > 0 = rotateLeft $ makeNode val left (rotateRight right)
    | otherwise = tree
  where
    bf = balanceFactor tree
balance Empty = Empty

-- In-order traversal
inOrder :: AVLTree a -> [a]
inOrder Empty = []
inOrder (Node val _ left right) = inOrder left ++ [val] ++ inOrder right

-- Example usage
main :: IO ()
main = do
    let tree = foldr insert Empty [10, 20, 30, 40, 50, 25]
    putStrLn $ "AVL Tree: " ++ show tree
    putStrLn $ "In-order traversal: " ++ show (inOrder tree)
    putStrLn $ "Tree height: " ++ show (height tree)