{- | Description: Construct a complete binary tree 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.P63". -} module Problems.P63 (completeBinaryTree, isCompleteBinaryTree) where import Problems.BinaryTrees import qualified Solutions.P63 as Solution -- $setup -- >>> import Problems.BinaryTrees {- | A complete binary tree with height \(h\) is defined as follows: * The levels 1, 2, 3, ..., \(h-1\) contain the maximum number of nodes, i.e., \(2^{i-1}\) at level \(i\). * On level \(h\), which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a level-order tree traversal all internal nodes come first, the leaves come second, and empty successors (the 'Empty's, which are not really nodes of the tree) come last. In particular, complete binary trees are used as data structures or addressing schemes for heaps. Write a function to construct a complete binary tree with the given number of nodes. === Examples >>> completeBinaryTree 4 Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty Empty) === __Hint__ We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node \(x\) with address \(a\), the following property holds: The address of \(x\)'s left and right successors are \(2^a\) and \(2^a + 1\), respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure. -} completeBinaryTree :: Int -> Tree () completeBinaryTree :: Int -> Tree () completeBinaryTree = Int -> Tree () Solution.completeBinaryTree -- | Write a function to return whether a tree is a complete binary tree. -- -- === Examples -- -- >>> isCompleteBinaryTree $ Branch () (Branch () Empty Empty) Empty -- True -- -- >>> isCompleteBinaryTree $ Branch () Empty (Branch () Empty Empty) -- False isCompleteBinaryTree :: Tree a -> Bool isCompleteBinaryTree :: forall a. Tree a -> Bool isCompleteBinaryTree = forall a. Tree a -> Bool Solution.isCompleteBinaryTree