{- |
Description: Construct completely 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.P55".
-}
module Problems.P55 (completelyBalancedTrees) where

import           Problems.BinaryTrees
import qualified Solutions.P55        as Solution

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

-- | In a completely balanced binary tree, the following property holds for every node:
-- The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal,
-- which means their difference is not greater than one.
--
-- Write a function to construct completely balanced binary trees for a given number of nodes.
--
-- === Examples
--
-- >>> printTreeList $ completelyBalancedTrees 4
-- [ Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty Empty)
-- , Branch () (Branch () Empty Empty) (Branch () (Branch () Empty Empty) Empty)
-- , Branch () (Branch () Empty Empty) (Branch () Empty (Branch () Empty Empty))
-- , Branch () (Branch () Empty (Branch () Empty Empty)) (Branch () Empty Empty) ]
completelyBalancedTrees :: Int -> [Tree ()]
completelyBalancedTrees :: Int -> [Tree ()]
completelyBalancedTrees = Int -> [Tree ()]
Solution.completelyBalancedTrees