The maximum number of nodes in a ternary tree with height h
a. (3^(h + 1) - 1 )/ 3 b. (3^h - 1) / 2 c. (3^h - 1 ) / 3 d. (3^(h + 1) - 1)/ 2
The answer is d. (3^(h + 1) - 1) /2
Ternary tree is like a binary tree where each node can have a maximum of 3 children.
At height 0 there is one node, at height 1 there are 3 nodes, at height 2 there are 3^2 nodes and the sequence goes on,
1, 3, 3^2, 3^3,.........................................3^h
if we solve this geometric progression, the answer will be (3^(h + 1) - 1) / (3 - 1) = ( 3^(h + 1) - 1) / 2
The maximum number of nodes in an 'm' ary tree with height h, where each node in the tree can have a maximum of m children is (m^(h+1) - 1) / (m - 1).
Suppose m=2 i.e. a binary tree, then maximum number of nodes in a binary tree of height h is (2^(h+1) - 1) / (2 - 1) = 2^(h+1) - 1.
Note: m^h is "m to the power of h" i.e 6^3=6 * 6* 6.
Share your thoughts in the comments below, to make me describe the blog post even better and do recommend the post if you found the content helpful!!!
