Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3?

if the maximum distance was 1, the answer would be 4.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might also want to take a look at meta.cs.stackexchange.com/q/1284/755. – D.W. Nov 5 '16 at 14:29

For a maximum distance of 3, your number of nodes would equal 7 or 8.

I read your question in such a way, that even the distance from one arbitrary node to another is at maximum 3. You get seven nodes if you imagine the following: The root node and the parents are a full tree with a total of four nodes, which equals your result for maximum distance 1. If you now add a single node to one of the child nodes, you immediately jump to a distance of 3, since you now can go from this child's child node to another child node via the root node. The only options to add other nodes to this tree is now to fill the child section of the node you already started with. Some exemplary tree could look like this:

  1
/ | \
2 3  4
/ | \
5  6  7


Another possible solution is assuming that you do not have to fill up your root level before starting another level, so you could add another root node which is only linking to one other node (which would be the root node of the first solution, looking like this:

  1
|
2
/ | \
3 4  5
/ | \
6  7  8


Your result would obviously differ if it was only concerning the distance from your root node to the furthest child (which is usually more common in trees), but I hope this is a satisfying answer.

• I forgot to explain why i did add to only one child node: – dennlinger Nov 5 '16 at 12:41
• If you would add to another child node, your path from one of the child-child nodes to another child-child node (but from another child-node) would equal 4, which would not satisfy your condition any longer – dennlinger Nov 5 '16 at 12:42