CODEWITHSUNDEEP
functionhaskelltreebinary-tree
Homes
Homes

Reputation: 31

Testing if binary tree is balanced in Haskell

what is another way to test whether a binary tree is balanced other than recursively calling the size function on the left and right subtrees. abs(size left - size right) <= 1 for the tree to be balanced. I must write an efficient function to satisfy the requirement but like i said does not recursively call the size function on the left and right subtrees.

Upvotes: 1

Views: 3422

Answers (5)

yairchu
yairchu

Reputation: 24814

You could use a type guaranteed Red-Black Tree. No need to check if it is balanced because the types assure it.

isBalanced = const True

Upvotes: 1

dave4420
dave4420

Reputation: 47072

The point about efficiently determining whether a tree is balanced without paying attention to its size, is that once you know the right branch is more than one level deeper than the left branch, it doesn't matter exactly how much deeper it is. 2 levels deeper? 3? 100? We don't care, and it could be considered inefficient to find out only to throw away the result.

isBalanced :: BinaryTree a -> Bool
isBalanced = and . treeToBalanceSize

treeToBalanceSize :: BinaryTree a -> BalanceSize
treeToBalanceSize Empty      = []
treeToBalanceSize (Node l r) = True : mergeBalanceSizes (treeToBalanceSize l) (treeToBalanceSize r)

mergeBalanceSizes :: BalanceSize -> BalanceSize -> BalanceSize
mergeBalanceSizes []       []       = []
mergeBalanceSizes [x]      []       = [x]
mergeBalanceSizes []       [y]      = [y]
mergeBalanceSizes (x : xs) (y : ys) = (x && y) : mergeBalanceSizes xs ys
mergeBalanceSizes _        _        = [False]

type BalanceSize = [Bool]

Satisfy yourself that

  1. If tree is balanced and of size size, then treeToBalanceSize tree = replicate size True.
  2. If tree is unbalanced, then treeToBalanceSize tree will end with a False.
  3. Evaluating mergeBalanceSizes [True] list does not cause list to be evaluated beyond its third element.

Upvotes: 0

Alex M
Alex M

Reputation: 3513

You could define a new binary tree that stores it's depth. Depth is updated on insert and removal, and you can tell if it's balanced by looking at the stored depth value.

It is a nicer solution to calculate recursively depending on how often you are updating the tree. It's cleaner anyway.

Upvotes: 0

ephemient
ephemient

Reputation: 204994

So it's pretty easy with recursion, isn't it?

import Data.Maybe (isJust)

getBalancedSize :: (Monad m, Num b, Ord b) => BinaryTree a -> m b
getBalancedSize Empty = return 0
getBalancedSize (Node _ l r) = do
    sizeL <- getBalancedSize l
    sizeR <- getBalancedSize r
    if abs (sizeL - sizeR) <= 1
        then return $ sizeL + sizeR + 1
        else fail "tree is not balanced"

isBalanced :: BinaryTree a -> Bool
isBalanced = isJust . getBalancedSize

Now suppose you have

fold :: (a -> b -> b -> b) -> b -> Tree a -> b
fold _ b Empty = b
fold f b (Node a l r) = f a (fold f b l) (fold f b r)

There's an obvious way to refactor getBalancedSize to be a single call to fold.

getBalancedSize = fold f (return 0) where
    f _ l r = do
        sizeL <- getBalancedSize l
        sizeR <- getBalancedSize r
        if abs (sizeL - sizeR) <= 1
            then return $ sizeL + sizeR + 1
            else fail "tree is not balanced"

But you do need some recursive function to walk the recursive tree structure.

Upvotes: 2

spyros
spyros

Reputation: 5

It depends on how your binary tree is represented in Haskell. If it's a recursive data structure, recursion is your only weapon...

Upvotes: 1

Related Questions