What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
- 18 Answers
- 47116 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
Explain what are the methods available in storing sequential files ?
How do you sort an array by value?
What is difference between rb tree and avl tree?
which is the simplest file structure? (Sequential, indexed, random)
What are examples of data structures?
Can a class have a constructor?
Run time memory allocation is known as in data structure?
What are the issues that hamper the efficiency in sorting a file?
Explain the terms base case, recursive case, binding time, run-time stack and tail recursion.
When is a graph said to be weakly connected?
Is python good for freshers?
How to compare Two Arrays?
What is adt example?
What is the best complexity of bubble sort?
What is the use of bubble sort?
