August 27, 2024

P59 - Construct height-balanced binary trees.

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 Tree.hbalTrees to construct height-balanced binary trees for a given height with a supplied value for the nodes.  The function should generate all solutions.

scala

scala> Tree.hbalTrees(3, "x")
res0: List[Node[String]] = List(T(x T(x T(x . .) T(x . .)) T(x T(x . .) T(x . .))), T(x T(x T(x . .) T(x . .)) T(x T(x . .) .)), ... 
Be first to comment
Leave a reply