Haskell binary tree with values only in leaves

Question

I would like to create a data type which represents a binary tree which has the values stored only in the leaves, then a function sub to check if a tree is subtree of other tree. Here is my code, but I got no idea how to implement the function sub.

data BinaryTree a = Leaf a | Node (BinaryTree a) (BinaryTree a)  deriving Show

makeBinTree :: [a] -> BinaryTree a
makeBinTree lst = head $ mrg leaves
where
  leaves = map (\x -> Leaf x) lst
  mrg [] = []
  mrg [x] = [x]
  mrg (x:y:xs) = mrg ( (Node x y) : mrg xs)

sub :: Eq a => BinaryTree a -> BinaryTree a -> Bool

michael_wu · Accepted Answer · 2016-04-17 22:29:04Z

2

First, you need a function to see if two trees are equal. You can derive Eq or implement something recursively like this

eq :: Eq a => BinaryTree a -> BinaryTree a -> Bool
eq (Leaf x) (Leaf y) = x == y
eq (Node l1 r1) (Node l2 r2) = (l1 `eq` l2) && (r1 `eq` r2)
eq _ _ = False

With that you can do

sub :: Eq a => BinaryTree a -> BinaryTree a -> Bool
sub s (Leaf y) = s `eq` Leaf y
sub s t@(Node l r) = s `eq` t || sub s l || sub s r

The first tree is a sub-tree of the second if both are equal or it is a sub-tree of the left or the right sub-tree.

answered Apr 17, 2016 at 22:29

michael_wu

16k5 gold badges66 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Christopher King Over a year ago

Word of warning: This is probably quite inefficient. I'm not sure if there is a more efficient way or not.

Collectives™ on Stack Overflow

Haskell binary tree with values only in leaves

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related