1
$\begingroup$

I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$ size(l) < 2^{h(l)} \\ size(r) < 2^{h(r)} $

where $l$ and $r$ are the left and right subtrees of the tree $t = \langle l,v,r \rangle$. Usually what I'd do is start from $size(\langle l,v,r \rangle)$ and work my way up to $< 2^{h(\langle l,v,r \rangle)}$. However I wasn't able.

$\endgroup$
2
$\begingroup$

If a binary tree has height $h$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $2^{h-1}$ nodes at depth $h-1$ (the maximal depth), and so at most $1+2+\cdots+2^{h-1} = 2^h-1$ nodes in total.

You can also prove this by induction. When $h=1$, the tree consists only of a root, so at most $1=2^h-1$ vertices. Given a tree of height $h$, its two subtrees have height at most $h-1$, and so together contain at most $2(2^{h-1}-1)$ vertices. Together with the root, the tree contains at most $2(2^{h-1}-1)+1=2^h-1$ vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.