Minimum number of nodes is a quaternary tree of height 4

1

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?

Thanks!

2

A 4 level tree, each node having 4 nodes:
1 + 4 + 4 * 4 + 4 * 4 * 4 ?

3

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

4

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)

5

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.