data Nat = S Nat | Z deriving (Eq)
 
instance Ord Nat where
    Z   <= n   = True
    S n <= Z   = False
    S n <= S m = n <= m
 
    {-min (S n) (S m) = S (min n m)
    min  _     _    = Z-}
 
instance Enum Nat where
	fromEnum  Z    = 0
	fromEnum (S n) = fromEnum n + 1
 
data Tree = Empty | Node Integer Tree Tree
 
minHeight  Empty        = Z
minHeight (Node _  l r) = S (min (minHeight l) (minHeight r))
 
tree = Node 0 tree (Node 1 tree Empty)
 
-- mt = minHeight tree
 
-- min via (<=):
-- mt
-- S (min mt (S (min mt Z)))
-- S (min mt (S Z))
-- S (if mt <= S Z then mt else S Z)
-- S (if S (if mt <= S Z then mt else S Z) <= S Z then mt else S Z)
-- S (if (if mt <= S Z then mt else S Z) <= Z then mt else S Z)
-- S (if (if (S (if mt <= S Z then mt else S Z)) <= S Z then mt else S Z) <= Z then mt else S Z)
-- S (if (if (if mt <= S Z then mt else S Z) <= Z then mt else SZ) <= Z then mt else S Z) 
-- again (if mt <= S Z then mt else S Z)
 
-- recursive min:
-- mt
-- S (min mt (S (min mt Z)))
-- S (min mt (S Z))
-- S (min (S (min mt (S Z))) (S Z))
-- S (S (min (min mt (S Z)) Z))
-- S (S (min (S ...) Z))
-- S (S Z)
 
main = print $ fromEnum $ minHeight tree -- 2

ZGF0YSBOYXQgPSBTIE5hdCB8IFogZGVyaXZpbmcgKEVxKQoKaW5zdGFuY2UgT3JkIE5hdCB3aGVyZQogICAgWiAgIDw9IG4gICA9IFRydWUKICAgIFMgbiA8PSBaICAgPSBGYWxzZQogICAgUyBuIDw9IFMgbSA9IG4gPD0gbQogICAgCiAgICB7LW1pbiAoUyBuKSAoUyBtKSA9IFMgKG1pbiBuIG0pCiAgICBtaW4gIF8gICAgIF8gICAgPSBaLX0KCmluc3RhbmNlIEVudW0gTmF0IHdoZXJlCglmcm9tRW51bSAgWiAgICA9IDAKCWZyb21FbnVtIChTIG4pID0gZnJvbUVudW0gbiArIDEKCmRhdGEgVHJlZSA9IEVtcHR5IHwgTm9kZSBJbnRlZ2VyIFRyZWUgVHJlZQoKbWluSGVpZ2h0ICBFbXB0eSAgICAgICAgPSBaCm1pbkhlaWdodCAoTm9kZSBfICBsIHIpID0gUyAobWluIChtaW5IZWlnaHQgbCkgKG1pbkhlaWdodCByKSkKCnRyZWUgPSBOb2RlIDAgdHJlZSAoTm9kZSAxIHRyZWUgRW1wdHkpCgotLSBtdCA9IG1pbkhlaWdodCB0cmVlCgotLSBtaW4gdmlhICg8PSk6Ci0tIG10Ci0tIFMgKG1pbiBtdCAoUyAobWluIG10IFopKSkKLS0gUyAobWluIG10IChTIFopKQotLSBTIChpZiBtdCA8PSBTIFogdGhlbiBtdCBlbHNlIFMgWikKLS0gUyAoaWYgUyAoaWYgbXQgPD0gUyBaIHRoZW4gbXQgZWxzZSBTIFopIDw9IFMgWiB0aGVuIG10IGVsc2UgUyBaKQotLSBTIChpZiAoaWYgbXQgPD0gUyBaIHRoZW4gbXQgZWxzZSBTIFopIDw9IFogdGhlbiBtdCBlbHNlIFMgWikKLS0gUyAoaWYgKGlmIChTIChpZiBtdCA8PSBTIFogdGhlbiBtdCBlbHNlIFMgWikpIDw9IFMgWiB0aGVuIG10IGVsc2UgUyBaKSA8PSBaIHRoZW4gbXQgZWxzZSBTIFopCi0tIFMgKGlmIChpZiAoaWYgbXQgPD0gUyBaIHRoZW4gbXQgZWxzZSBTIFopIDw9IFogdGhlbiBtdCBlbHNlIFNaKSA8PSBaIHRoZW4gbXQgZWxzZSBTIFopIAotLSBhZ2FpbiAoaWYgbXQgPD0gUyBaIHRoZW4gbXQgZWxzZSBTIFopCgotLSByZWN1cnNpdmUgbWluOgotLSBtdAotLSBTIChtaW4gbXQgKFMgKG1pbiBtdCBaKSkpCi0tIFMgKG1pbiBtdCAoUyBaKSkKLS0gUyAobWluIChTIChtaW4gbXQgKFMgWikpKSAoUyBaKSkKLS0gUyAoUyAobWluIChtaW4gbXQgKFMgWikpIFopKQotLSBTIChTIChtaW4gKFMgLi4uKSBaKSkKLS0gUyAoUyBaKQoKbWFpbiA9IHByaW50ICQgZnJvbUVudW0gJCBtaW5IZWlnaHQgdHJlZSAtLSAy