0
$\begingroup$

It's the continuation of the exercise: https://cs.stackexchange.com/questions/65384/tree-elements-influence-on-another-elements-searching-for-specific-elements

I need to say how many elements do I have in specific subtrees.

Input: n - how many elements are in the tree, k - around how many elements should be in the subtree, and then I have got n-1 numbers p, which are saying who is the parent from the node. Node number is the number of the line.

Example Input:

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

The question is: how many elements have got the subtree(1) and subtree(2). The subtree(2) should be also the subtree of subtree(1). Subtree(1) has got a number of elements which is greater than k, but the number of elements should be as near as possible to k. Subtree(2) should be the subtree of subtree(1) and its number of elements is equal or less than k, also it should be the as near as possible to k.

                    3 
                    | \ 
                    7  9               subtree(1) - 6 elements >k
                    |  | \
                    8  10 11

                           9               subtree(2) - 3 elements <= k
                           | \ 
                           10 11

For the Example Input, the answer is: 6 - subtree(1) and 3 - subtree(2).

Why not the subtree which starts from 2? Because:

            2      It has got 4 elements <= k, so I must then take the whole 
          / | \    tree which has got 11 elements >k. The subtree(1) has got 
         4  5  6   less elements - 6, where k = 4. 6-4 < 11-4.

Why not the subtree which starts from 7? Because:

        7     It has got 2 elements <= k, this is the subtree of 
        |     subtree(1), where k = 4. But beside we have got a subtree(2),
        8     which has got 3 elements. 4-3 < 4-2.

I was thinking about:

  1. Storing all the childrens, indirect and direct childrens, for example, that the node 3 has got 5 childrens, node 9 has got 2 childrens. But I think it's quite slow if I would get the max number n = 500000, and all of the nodes would have got 1 direct parent, that would be probably too slow.
  2. Making a normal tree data structure with std::vector, but I don't have any further idea to this.
$\endgroup$
  • $\begingroup$ Why doesn't any post-order traversal algorithm (or plain recursion, really) solve your problem? $\endgroup$ – Raphael Nov 7 '16 at 19:13
  • $\begingroup$ Could you tell me a link for some guide to this algorithm? Everything that I found it's about a binary tree. $\endgroup$ – StarterInThis Nov 7 '16 at 19:37
  • 1
    $\begingroup$ I can't understand the problem you're trying to solve. What do you mean when you say that $k$ is "around how many elements should be in the subtree"? What subtree? You haven't mentioned any subtree. How "around"? Also, talking about std::vector makes it sound like you're looking for coding help, which is off-topic, here. $\endgroup$ – David Richerby Nov 7 '16 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.