CODEWITHSUNDEEP
haskellbinary-tree
Georgi Angelov
Georgi Angelov

Reputation: 4388

Haskell : Comparing if two binary trees have the same elements

So I am working on a function that detects if two binary trees have the same numbers in them.

So what I've come up with is the following which works just fine but the problem is that I am using total of 5 functions. Is there another way of detecting if two BT's have the same elements with just one function ? Here is my solution so far which seems to work just fine.

flatten :: BinTree a -> [a]
flatten Empty        = []
flatten (Node l x r) = flatten l ++ [x] ++ flatten r

splt :: Int -> [a] -> ([a], [a])
splt 0 xs = ([], xs)
splt _ [] = ([],[])
splt n (x:xs) = (\ys-> (x:fst ys, snd ys)) (splt (n-1) xs)

merge :: Ord a => [a] -> [a] -> [a] 
merge xs [] = xs
merge [] ys = ys    
merge (x:xs) (y:ys) = if (x > y) then y:merge (x:xs) ys else x:merge xs(y:ys)

msort :: Ord a => [a] -> [a]
msort [] =[]
msort (x:[]) = (x:[])
msort xs = (\y -> merge (msort (fst y)) (msort (snd y))) (splt (length xs `div` 2) xs)

areTreesEqual :: (Ord a) => BinTree a -> BinTree a-> Bool
areTreesEqual Empty Empty = True
areTreesEqual Empty a = False
areTreesEqual a Empty = False
areTreesEqual a b = msort (flatten (a) ) == msort (flatten (b))

Upvotes: 0

Views: 1346

Answers (1)

daniel gratzer
daniel gratzer

Reputation: 53911

How about

import Data.MultiSet as Set

equal a b = accum a == accum b
  where accum Empty = Set.empty
        accum (Node l x r) = Set.insert x (accum l `Set.union` accum r)

Sets are lovely for unordered comparison and multisets will make sure that

 1   /=   1
1 1

Eg, that duplicate numbers are counted properly. If this isn't a big concern, than swap MultiSet for Set. I think 3 lines is pretty decent for this sort of thing.

Upvotes: 1

Related Questions