CODEWITHSUNDEEP
algorithmbinary-tree
Muwei He
Muwei He

Reputation: 45

How to find all rooted subtrees of at most size K in a given binary tree?

As title. How to efficiently generate all those subtrees that share the same root with the original binary tree?

Upvotes: 2

Views: 189

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65488

It's pretty similar to generating all unlabeled binary trees of size k, whose algorithm looks like this:

trees(k):
    if k is zero:
        yield the null tree
    else:
        for i from 0 to k-1:
            for l in trees(i):
                for r in trees(k-i):
                    yield the tree whose root has left subtree l
                        and right subtree r

You should be able to find a concrete implementation of this in your favorite programming language.

To solve the question, we modify this code to take apart the given tree alongside the recursion.

subtrees(T, k):
    if k is zero:
        yield the null tree
    else if T is not null:
        let L be the left subtree of T's root
        let R be the right subtree of T's root
        for i from 0 to k-1:
            for l in subtrees(L, i):
                for r in subtrees(R, k-i):
                    yield the tree whose root has the same value as T's,
                        with left subtree l and right subtree r

Upvotes: 3

Related Questions