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

Some solutions to "Problems.P55" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P55 (completelyBalancedTrees) where

import           Problems.BinaryTrees

-- | Constructs completely balanced binary trees for a given number of nodes.
completelyBalancedTrees :: Int -> [Tree ()]
completelyBalancedTrees :: Int -> [Tree ()]
completelyBalancedTrees Int
0 = [Tree ()
forall a. Tree a
Empty]
completelyBalancedTrees Int
n
  | Int -> Bool
forall a. Integral a => a -> Bool
even Int
n    = Int -> Int -> [Tree ()]
generate (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) ((Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [Tree ()] -> [Tree ()] -> [Tree ()]
forall a. [a] -> [a] -> [a]
++
                Int -> Int -> [Tree ()]
generate ((Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)
  | Bool
otherwise = Int -> Int -> [Tree ()]
generate (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)

generate :: Int -> Int -> [Tree ()]
generate :: Int -> Int -> [Tree ()]
generate Int
m Int
n = [() -> Tree () -> Tree () -> Tree ()
forall a. a -> Tree a -> Tree a -> Tree a
Branch () Tree ()
l Tree ()
r | Tree ()
l <- [Tree ()]
ltrees, Tree ()
r <- [Tree ()]
rtrees]
  where ltrees :: [Tree ()]
ltrees = Int -> [Tree ()]
completelyBalancedTrees Int
m
        rtrees :: [Tree ()]
rtrees = Int -> [Tree ()]
completelyBalancedTrees Int
n