| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P60
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P60.
Synopsis
- heightBalancedTreesWithNodes :: Int -> [Tree ()]
Documentation
heightBalancedTreesWithNodes :: Int -> [Tree ()] Source #
Construct all the height-balanced binary trees with a given number of nodes.
Examples
>>>length $ heightBalancedTreesWithNodes 151553
>>>mapM_ printTreeList $ map heightBalancedTreesWithNodes [0..3][ Empty ] [ Branch () Empty Empty ] [ Branch () (Branch () Empty Empty) Empty , Branch () Empty (Branch () Empty Empty) ] [ Branch () (Branch () Empty Empty) (Branch () Empty Empty) ]
Hint
Consider a height-balanced binary tree of height \(h\). What is the maximum number of nodes it can contain? Clearly, it is \(2^h-1\).
However, what is the minimum number of nodes it can contain? This question is more difficult. Try to find a recursive statement and turn it into a function that returns the minimum number of nodes in a height-balanced binary tree of height \(h\).
On the other hand, what is the maximum height \(h\) a height-balanced binary tree with \(n\) nodes can have? What about the minimum height? Try writing functions to compute these.
Notes
The original problem asked to implement functions computing the minimum number of nodes for a given height and the maximum height for a given number of nodes. These are more of a hint as to how to implement the main function in question, so they were made hints instead of being part of the problem itself.