What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
- 18 Answers
- 47161 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 exactly is data?
How do I start preparing for placement?
How does insertion sort works?
Write a recursive c function to calculate the height of a binary tree.
Is array of data structure?
What is difference between linear and non linear data structure?
How to do the intersection of two sorted arrays?
Differentiate bfs and dfs?
Find duplicates in infinite range. Which data structure to be used to give efficient solution?
Explain what is the type of the algorithm used in solving the 8 queens problem?
What is data type in data structure?
Which sorting algorithm uses minimum number of swaps?
What is the difference between array and stack?
Define graph?
What is difference between tree and forest?
