haskell create an unbalanced tree

Question

My Tree definition is

data Tree = Leaf Integer | Node Tree Tree

This is a binary tree, with only values at the leaves. I am given following definition for balanced trees:

We say that a tree is balanced if the number of leaves in the left and right subtree of every node differs by at most one, with leaves themselves being trivially balanced.

I try to create a balanced tree as follows:

t :: Tree

t = Node (Node (Node (Leaf 1) (Leaf 2)) (Node(Leaf 3)(Leaf 4))) (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)) )

Can you please let me know if t above is a balanced tree with values only at the leaves?

Another question, how do I create another tree with values only at the leaves and it is unbalanced as per above definition.

Thanks

dfeuer dfeuer · Accepted Answer · 2015-12-11T05:46:01

Can you please let me know if t above is a balanced tree with values only at the leaves?

I can, but I won't. However, I hope I can guide you through the process of writing a function that will determine whether a given tree is balanced.

The following is certainly not the most efficient way to do it (see the bottom for a hint about that), but it is a very modular way. It's also a good example of the "computation by transformation" approach that functional programming (and especially lazy functional programming) encourages. It seems pretty clear to me that the first question to ask is "how many leaves descend from each node?" There's no way for us to write down the answers directly in the tree, but we can make a new tree that has the answers:

data CountedTree = CLeaf Integer | CNode Integer Tree Tree

Each node of a CountedTree has an integer field indicating how many leaves descend from it.

You should be able to write a function that reads off the total number of leaves from a CountedTree, whether it's a Leaf or a Node:

getSize :: CountedTree -> Integer

The next step is to determine whether a CountedTree is balanced. Here's a skeleton:

countedBalanced :: CountedTree -> Bool
countedBalanced CLeaf = ?
countedBalanced (CNode _ left right)
  = ?? && ?? && getSize left == getSize right

I've left the first step for last: convert a Tree into a CountedTree:

countTree :: Tree -> CountedTree

And finally you can wrap it all up:

balanced :: Tree -> Bool
balanced t = ?? (?? t)

Now it turns out that you don't actually have to copy and annotate the tree to figure out whether or not it's balanced. You can do it much more directly. This is a much more efficient approach, but a somewhat less modular one. I'll give you the relevant types, and you can fill in the function.

-- The balance status of a tree. Either it's
-- unbalanced, or it's balanced and we store
-- its total number of leaves.
data Balance = Unbalanced | Balanced Integer

getBalance :: Tree -> Balance

haskell create an unbalanced tree

1 Answers