Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

noob_master's blog

How to form a k-nary tree with x leaf nodes.
By noob_master, history, 5 years ago, In English

How to form a k-nary tree with x leaf nodes.
Is there any way to find whether a k-nary tree(every node has either k child or it is a leaf node) which have x leaf nodes exists or not. If exits then how to find it.

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unless I’m missing something, you can make an arbitrary k-ary tree with any number of nodes.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Work through a few small examples and look for a pattern that can be generalized.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I asked the question after trying. Nevertheless, I will try again.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let’s walk through some examples together.

      For any k, we can start with a k-ary tree of 1 node. Each time we want to go from a k-ary tree of a certain size to the one of the next smallest possible size, we will choose a leaf node and make it an internal node with k children (which are leaves).

      k=2
      k=3
      k=11

      ...

      Result
      → Reply