This is not much of a coding question but it has to do generally with data structures and trees. Suppose we have in java a quaternary tree with height 4 and we want to find the minimum number of nodes it can contain. I thought that since all internal nodes of a quaternary tree have to contain 4 nodes the minimum number of nodes would be 17 but I am not really sure. Any other opinions?
A 4 level tree, each node having 4 nodes:
1 + 4 + 4 * 4 + 4 * 4 * 4 ?
My thought was that it should be something like 1 + 4 + 4 + 4 + 4, because every time we will be moving we would using one node leaving the others as leaf nodes. But I am not sure if in a quaternary tree each internal node should contain 4 sub-nodes
If the deepest level can hold one node each only then
1 + 4 + 4*4 + 4*4
Edit: that assumes that the tree is filled evenly.
If the tree is not filled evenly then the minimum number is 4 (every level has one node)