{- |
Description: Construct height-balanced binary trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P59".
-}
module Problems.P59 (heightBalancedTrees) where

import           Problems.BinaryTrees
import qualified Solutions.P59        as Solution

-- $setup
-- >>> import Problems.BinaryTrees

-- | In a height-balanced binary tree, the following property holds for every node:
-- The height of its left subtree and the height of its right subtree are almost equal,
-- which means their difference is not greater than one.
--
-- Construct a list of all height-balanced binary trees with the given maximum height.
--
-- === Examples
--
-- >>> printTreeList $ heightBalancedTrees 2
-- [ Branch () (Branch () Empty Empty) Empty
-- , Branch () (Branch () Empty Empty) (Branch () Empty Empty)
-- , Branch () Empty (Branch () Empty Empty) ]
--
-- >>> length $ heightBalancedTrees 4
-- 315
heightBalancedTrees :: Int -> [Tree ()]
heightBalancedTrees :: Int -> [Tree ()]
heightBalancedTrees = Int -> [Tree ()]
Solution.heightBalancedTrees