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

Some solutions to "Problems.P63" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P63 (completeBinaryTree, isCompleteBinaryTree) where

import           Problems.BinaryTrees

-- | Construct a complete binary tree with the given number of nodes.
completeBinaryTree :: Int -> Tree ()
completeBinaryTree :: Int -> Tree ()
completeBinaryTree Int
n = Int -> Int -> Tree ()
buildTree Int
n Int
1

buildTree :: Int -> Int -> Tree ()
buildTree :: Int -> Int -> Tree ()
buildTree Int
size Int
index
  | Int
index Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
size = () -> Tree () -> Tree () -> Tree ()
forall a. a -> Tree a -> Tree a -> Tree a
Branch () (Int -> Int -> Tree ()
buildTree Int
size (Int -> Tree ()) -> Int -> Tree ()
forall a b. (a -> b) -> a -> b
$ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
index) (Int -> Int -> Tree ()
buildTree Int
size (Int -> Tree ()) -> Int -> Tree ()
forall a b. (a -> b) -> a -> b
$ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
index Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  | Bool
otherwise     = Tree ()
forall a. Tree a
Empty

-- | Write a function to return whether a tree is a complete binary tree.
isCompleteBinaryTree :: Tree a -> Bool
isCompleteBinaryTree :: forall a. Tree a -> Bool
isCompleteBinaryTree Tree a
t = Tree a -> Int -> Int -> Bool
forall a. Tree a -> Int -> Int -> Bool
isTree Tree a
t (Tree a -> Int
forall a. Tree a -> Int
treeSize Tree a
t) Int
1

isTree :: Tree a -> Int -> Int -> Bool
isTree :: forall a. Tree a -> Int -> Int -> Bool
isTree Tree a
Empty Int
size Int
index = Int
index Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
size
isTree (Branch a
_ Tree a
l Tree a
r) Int
size Int
index = Int
index Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
size Bool -> Bool -> Bool
&& Tree a -> Int -> Int -> Bool
forall a. Tree a -> Int -> Int -> Bool
isTree Tree a
l Int
size (Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
index) Bool -> Bool -> Bool
&& Tree a -> Int -> Int -> Bool
forall a. Tree a -> Int -> Int -> Bool
isTree Tree a
r Int
size (Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
indexInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)