Copyright	Copyright (C) 2021 Yoo Chung
License	GPL-3.0-or-later
Maintainer	dev@chungyc.org
Safe Haskell	Safe-Inferred
Language	GHC2021

Problems.P63

Description

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P63.

Synopsis

completeBinaryTree :: Int -> Tree ()
isCompleteBinaryTree :: Tree a -> Bool

Documentation

completeBinaryTree :: Int -> Tree () Source #

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 Emptys, 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

Expand

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.

isCompleteBinaryTree :: Tree a -> Bool Source #

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