CODEWITHSUNDEEP
algorithmtree
Love Paper
Love Paper

Reputation: 471

Select the subtrees containing exactly K leaves

I'm given a tree T which has n nodes and l leaves.

I have to select some subtrees which contains exactly k (<=l) leaves. If I select node t's ancestors' subtree, we cannot select t's subtree.

For example:

enter image description here

This is the tree T which has 13 nodes (7 leaves).

If I want to select k = 4 leaves, I can select node 4 and 6 (or, node 2 and 5). This is the minimum number of the selection. (we can select node 6, 7, 8, 9 either, but this is not the minimum).

If I want to select k = 5 leaves, I can select node 3, and this is the minimum number of the selection.

I want to select the minimum numbers of subtrees. I can find only O(nk^2) and O(nk) algorithm, which uses BFS and dynamic programming. Is there any better solution with selecting this?

Thanks :)

Upvotes: 2

Views: 495

Answers (1)

alestanis
alestanis

Reputation: 21863

Actually, to know the number of leaves of each subtree you just need to go through each node once so complexity should be O(nm) where m is the mean number of children of each node, which in most cases evaluates to O(n) because m is just a constant. To do this, you should:

  • Find which nodes of your tree are leaves
  • Go up the tree, saving for each node the number of leaves in its subtree

You can do this by starting with leaves and putting parents inside a queue. When you pop a node n_i out of the queue, sum the number of leaves contained in each subtree starting from each of n_i's children. Once you're done, mark n_i as visited (so you don't visit it multiple times, since it can be added once per children)

This gives something like this:

^
|               f (3)              This node last
|              / \
|            /     \
|          /         \
|        /             \
|       d (2)           e (1)      These nodes second
|      /  \            /
|     /    \          / 
|    a (1)  b (1)    c (1)         These nodes first

The steps would be:

Find leaves `a`, `b` and `c`.
For each leave, add parent to queue   # queue q = (d, d, e)

Pop d                                 # queue q = (d, e)
Count leaves in subtree: d.leaves = a.leaves + b.leaves
Mark d as visited
Add parent to queue                   # queue q = (d, e, f)

Pop d                                 # queue q = (e, f)
d is visited, do nothing

Pop e                                 # queue q = (f)
Count leaves in subtree: e.leaves = c.leaves
Mark d as visited
Add parent to tree                    # queue q = (f, f)

Pop f                                 # queue q = (f)
Count leaves in subtree: f.leaves = d.leaves + e.leaves
Mark d as visited
Add parent to tree (none)

Pop f                                 # queue q = ()
f is visited, do nothing

You can also use a smart data structure that will ignore nodes added twice. Note that you can't use an ordered set because it is very important that you explore "lower" nodes before "higher" nodes.

In your case, you can eliminate nodes in your queue if they have more than k leaves, and return each node that you find that haves k leaves, which will give an even faster algorithm.

Upvotes: 2

Related Questions