Search code examples
haskellbinary-treesubtree

Haskell: return a list of all substrees in Binary Tree. Is my code correct?

So I am trying to implement a functoin in Haskell that accepts a Binary Tree and returns a list of all subtrees where order and repetition does not matter but all substrees must be present at least once. Here is my code:

data BinTree a = Empty | Node (BinTree a) a (BinTree a) deriving (Eq,Show)

subtrees :: BinTree a -> [BinTree a]
subtrees Empty = [Empty]
subtrees (Node tL x tR) = [Node tL x tR] ++ subtrees tL ++ subtrees tR

Here is my data set

(Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty))

Here is my result

[Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty),
Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty,Node (Node Empty 1 Empty) 1 Emp
ty,Node Empty 1 Empty,Node Empty 2 Empty]

For some reason I am somewhat doubtful of this implementation and I would appreciate any feedback! Thanks!

Solution

  • Looks ok. Only answer the question: what is a list of all subtrees of a Empty tree?