Finding all subtrees of n-ary tree

Question

I am trying to find all subtrees of n-ary tree. Only BFS or DFS does not work. Because the tree is not binary. For example:

        1
     /    \
    2      3
   / \    /|\
  4   6  5 7 8
        / \
       9   10

I want to show all subtrees including this one

        1
     /    \
    2      3
     \     |
      6    7

How can I extract this subtree from original one?

Answer 1

To generate all (graph-theoretic) subtrees of a given tree, I will need some auxiliary notions.

A subtree is a connected subgraph pf a tree, or equivalently, a subgraph which is also a tree.

A descendant tree of a rooted tree is either the original rooted tree itself, or a rooted tree which is a child of one of its vertices. (Won't give an exact definition here as it should be clear from the notion of a tree as a recursive data structure).

A rooted subtree of a rooted tree is a subtree that has the same root as the original rooted tree. We can get a rooted subtree of a rooted tree by computing rooted subtrees of (some of) immediate children of the root, and combining those with the original root.

Note that an arbitrary subtree is a rooted subtree of a descendant tree.

I will deal with non-empty trees for simplicity.

-- a (rooted) tree is a root node and a list of children attached to it
data Tree a = Node a [Tree a] deriving Show

It is straightforward to get the descendants:

-- a descendant tree  is either a tree itself, 
-- or a descendant of a child of its root
descendants :: Tree a -> [Tree a]
descendants t@(Node a ts) = t : concatMap descendants ts

Rooted subtrees are not much harder:

-- to get a rooted subtree, take a root, choose which children to 
-- retain, take a rooted subtree of each retained child, 
-- and attach the results to a copy of the root

rootedSubtrees :: Tree a -> [Tree a]
rootedSubtrees (Node a ts) = [Node a tts | 
                              tts <- choices (map rootedSubtrees ts)]

-- this function receives a list of lists and generates all lists that 
-- contain 0 or 1 element from each input list
-- for ex. choices ["ab", "cd"] = ["","c","d","a","ac","ad","b","bc","bd"]
choices :: [[a]] -> [[a]]
choices [] = [[]]
choices (xs:xxs) = cs ++ [x:c | x <- xs, c <- cs] where cs = choices xxs

Finally, the list of arbitrary subtrees is

subtrees :: Tree a -> [Tree a]
subtrees t = concatMap rootedSubtrees (descendants t)