What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
- 18 Answers
- 47035 Views
- CSC, National Instruments, Sasken, Sybrant Technologies, I also Faced
- E-Mail Answers
Answer Posted / hex
to be more generic this kind of problem is best solved
recursivly.
To point out that 2 ^ N AND 3 ^ N are both wrong,
here's a few examples: (the exponet is the amount of levels)
2^0 = 1, correct
2^1 = 2, incorrect, should be 3
2^2 = 4, incorrect, should be 7
And a tree with three children
3^0 = 1, correct
3^1 = 3, incorrect, should be 4
3^2 = 9, incorrect, should be 13
Looking at that I'm sure you can see the pattern.
Let
C = "Number of Possible Children"
N = Levels
N
Σ C^N
j=0
or in C++ code
int NodeCount(int C, int N)
{
if (N < 0) return 0
return NodeCount(C, N-1) + C^N
}
| Is This Answer Correct ? | 8 Yes | 4 No |
Post New Answer View All Answers
What sort does arrays sort use?
What are the scenarios in which an element can be inserted into the circular queue?
What is binary tree in discrete mathematics?
What is array and string?
Who invented merge sort?
How can you insert a node in a random location of the linked list?
What does simulation of queues mean?
What is the complexity of arraylist?
What is the Role of push() and pop() method?
Is bubble sort slow?
If you are using c language to implement the heterogeneous linked list, explain what pointer type will you use?
How is the front of the queue calculated in data structure?
How do you find the time complexity of a bubble sort?
How do hash tables work?
What is difference between data type and variable?
