What is the maximum total number of nodes in a tree that has
N levels? Note that the root is level (zero)
- 18 Answers
- 49372 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 happens if we put duplicate key in hashmap?
How null key is handled in hashmap?
What do you mean by breadth first search (bfs)?
What is arrays copyof?
What is quick sort?
A lot of data structures related programs related to only trees and graphs, like the diameter of a tree, removing the loops in a graph etc.
What are the Differences between map and hashmap?
What is breadth first tree?
How do you sort an arraylist?
What is the difference between Strings and Arrays?
What are the types of collision resolution strategies in open addressing?
How to sort an Array?
write a program to show the insertion and deletion of an element in an array using the position
What is difference between hashmap and hashtable?
What is a priority queue?
