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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.