Function bottomSubtrees

The set of all bottom-grounded subtrees of a tree. This is the set of every subtree of the tree T that:

1. The subtree root is a node of T. Every node in T appears exactly once in its subtrees list as root node.
2. The leaves of the subtree are exactly the leaves reachable from its root node in the tree T. This makes it bottom-grounded.

The number of such subtrees of a tree is the number of nodes in the tree.

For example consider the tree:

┬root
├┬a
│├─b
│└─c
└┬d
 ├─e
 └─f
Copy

bottomSubtrees will return for this tree seven trees, one per node:

  1. ─b       4. ─e     7. ┬root
                           ├┬a
  2. ─c       5. ─f        │├─b
                           │└─c
  3. ┬a       6. ┬d        └┬d
     ├─b         ├─e        ├─e
     └─c         └─f        └─f
Copy