haskell - バランスの取れたツリーの Haskell チェック

Question

このツリーのバランスが取れていることを確認するにはどうすればよいですか?

data Tree a = Leaf a | Node (Tree a) (Tree a)

size :: Tree a -> Int
size (Leaf n)    = 1
size (Node x z) = size x + size z + 1

これは私がこれまでに持っているものです:

isBalancedTree :: Tree a -> Bool
isBalancedTree (Node l r) = abs (size l - size r) <= 1
                            && isBalancedTree l && isBalancedTree r
isBalancedTree _ = False

Answer 1

リーフはバランスが取れているため、最後の行は実際には に評価されTrue、次のようになります。

isBalancedTree :: Tree a -> Bool
isBalancedTree (Leaf _) = True
isBalancedTree (Node l r) = 
    let diff = abs (size l - size r) in
    diff <= 1 && isBalancedTree l && isBalancedTree r