New answers tagged

0 votes

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

Proof by picture. There is an straightforward bijection between the (binary) numbers $1$ to $\underbrace{1\dots 1}_k$ and the available node positions in a binary tree of $k$ levels (where we count te ...
Hendrik Jan's user avatar
  • 30.6k
0 votes

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

This is a classic textbook problem. You can find plenty of solutions online. A direct derivation can be made to prove the statement as well. For that, we would argue about two things: First, we argue ...
codeR's user avatar
  • 635
1 vote

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

You should really show what you tried before asking, this is not a site for answering homework questions. Still, some hints. You can use the principle of mathematical induction. Start with your base ...
codeing_monkey's user avatar
1 vote

Optimal Binary Search Trees Knuth

That proof in fact had an error, in exactly the step in the induction that your answer asks about. Knuth published an erratum about it the following year. See Item 2 in [1] (copied below). See also [...
Neal Young's user avatar

Top 50 recent answers are included