CODEWITHSUNDEEP
algorithmtreelanguage-agnostictree-traversal
Naman
Naman

Reputation: 2669

Number of ways to select K nodes from tree such that parent of node must be chosen if node is chosen

I am trying to solve this problem where I have a tree where each node can have any number of children. I have to find all possible ways to select K nodes such that any node is chosen only if it's parent is chosen.

I tried but am not able to find the solution. Can someone help me please? Basic algorithm (pseudo code) is enough.

Upvotes: 2

Views: 297

Answers (1)

user4668606
user4668606

Reputation:

We can use DFS to solve this problem. Consider each possible selection a vertex of a graph. An edge would accordingly exist between two vertices/selections, if we can transform one selection into another one by removing one vertex from the selection and add another valid tree-node to the selection. This graph is connected, thus we can traverse it by DFS.

E.g.:

input tree:       1              K=3
               /  |  \
              3   4   5
                /   /   \
               6   7     2

first solution (preorder traversal):
         1
      /  |
     3   4

consecutive solutions:
    removing node 3 from selection   removing node 4
         1         1                       1
         |         |  \                  /   \
         4         4   5                3     5
       /
      6

Since we need a start-vertex, to produce other vertices, we need a valid selection to start with. Simplest solution would be to traverse the tree preorder and select the first K nodes.

From that start-vertex, we can produce the entire graph on the run:
Basically each node contains a subtree from the input-tree, aka the selection. Take the selection from the node you just traverse. By removing an arbitrary leaf from the subtree represented by the selection, we gain a subtree/selection with K - 1 nodes. This selection can be completed to K nodes, by adding another node to the subtree that would be a new leaf. This approach would also match the definition of edges given above.

So now we know how to produce all adjacent vertices from a given vertex/selection. The rest is just a plain DFS-traversal. Mark the the vertex as visited, get all neighboring vertices, and perform a DFS-traversal on them, until all vertices have been visited.

Upvotes: 1

Related Questions