根の深さを0としたとき、高さが3の二分木が持つことのできる最大のノード数はいくつですか。

二分木では深さdの階層に最大2のd乗個のノードが存在できます。高さ3の木は深さ0から3までの4つの階層を持つため、最大ノード数は1+2+4+8=15となります。一般に高さhの二分木の最大ノード数は2の(h+1)乗から1を引いた値です。逆に言えば、n個のノードを持つ完全二分木の高さはおよそlog2 nとなり、これが二分探索木やヒープの操作がO(log n)になる根拠です。