Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

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

`>>>`

1553`length $ heightBalancedTreesWithNodes 15`

`>>>`

[ Empty ] [ Branch () Empty Empty ] [ Branch () (Branch () Empty Empty) Empty , Branch () Empty (Branch () Empty Empty) ] [ Branch () (Branch () Empty Empty) (Branch () Empty Empty) ]`mapM_ printTreeList $ map heightBalancedTreesWithNodes [0..3]`

### 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.