What is the maximum number of nodes in a binary tree of height h, where height is defined as the number of edges on the longest path from the root to a leaf?
Show answer
2^(h+1) - 1
This formula describes a 'perfect binary tree,' where every internal node has two children and all leaves are at the same maximum depth. A helpful way to remember this is that each new level added to the tree doubles the potential capacity of the level above it, resulting in a total that is always one less than a power of two.