{- |
Description: Height-balanced binary trees with given number of nodes
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.P60".
-}
module Problems.P60 (heightBalancedTreesWithNodes) where

import           Problems.BinaryTrees
import qualified Solutions.P60        as Solution

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

-- | Construct all the height-balanced binary trees with a given number of nodes.
--
-- === Examples
--
-- >>> length $ heightBalancedTreesWithNodes 15
-- 1553
--
-- >>> mapM_ printTreeList $ map heightBalancedTreesWithNodes [0..3]
-- [ Empty ]
-- [ Branch () Empty Empty ]
-- [ Branch () (Branch () Empty Empty) Empty
-- , Branch () Empty (Branch () Empty Empty) ]
-- [ Branch () (Branch () Empty Empty) (Branch () Empty Empty) ]
--
-- === __Hint__
--
-- Consider a height-balanced binary tree of height \(h\).
-- What is the maximum number of nodes it can contain? Clearly, it is \(2^h-1\).
--
-- However, what is the minimum number of nodes it can contain?  This question is more difficult.
-- Try to find a recursive statement and turn it into a function
-- that returns the minimum number of nodes in a height-balanced binary tree of height \(h\).
--
-- On the other hand, what is the maximum height \(h\) a height-balanced binary tree
-- with \(n\) nodes can have?  What about the minimum height?  Try writing functions to compute these.
--
-- === __Notes__
--
-- The original problem asked to implement functions computing the minimum number of nodes for a given height
-- and the maximum height for a given number of nodes.  These are more of a hint as to how to implement
-- the main function in question, so they were made hints instead of being part of the problem itself.
heightBalancedTreesWithNodes :: Int -> [Tree ()]
heightBalancedTreesWithNodes :: Int -> [Tree ()]
heightBalancedTreesWithNodes = Int -> [Tree ()]
Solution.heightBalancedTreesWithNodes