"In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Write a method to construct height-balanced binary trees for a given height with a supplied value for the nodes. The function should generate all solutions."

### Example

ninety-nine-clojure.bintrees> (height-balanced-trees 2 'x) ([x [x nil nil] [x nil nil]] [x [x nil nil] nil] [x nil [x nil nil]])

### Discussion

To get some intuition for this problem we can distinguish tree cases:- The left subtree has the same length as the right subtree
- The left subtree is shorter by one level
- The right subtree is shorter by one level

The practical applicability of the function just created as described is somewhat limited as the number of height balanced binary trees grows exponentially. For our test case we therefore just look at trees up to five levels high.

## No comments:

Post a Comment