0
$\begingroup$

I am attempting to find a formula that describes the number of leaf nodes in a full binary tree of depth k, therefore nodes at a depth <k have exactly two children and the leaves are at depth K.

This gives me the following pattern.
A tree with 1 Node has 1 Leaf
A tree with 3 Nodes has 2 leaves
A tree with 7 Nodes has 4 leaves
A tree with 15 Nodes has 8 leaves
A tree with 31 Nodes has 16 leaves

I am trying to figure out a formula that tells the number of leaves given N = Number of Nodes but have not been able to figure it out

$\endgroup$
  • 2
    $\begingroup$ Welcome to Stack Exchange. Have you spent at least 5 or 10 minutes trying to figure this out? If so, what did you try? Also, do you want to learn how to find the answer, or do you just want the answer? $\endgroup$ – Tanner Swett May 28 at 4:48
2
$\begingroup$

Hint: Add one to the number of nodes and compare it to the number of leaves. Do you see a pattern?

$\endgroup$
0
$\begingroup$

Hint: there exist $a$ and $b$ such that the number of leaves in a tree with $n$ nodes is $an+b$. Use two of the examples you've found already to find $a$ and $b$.

A tree with $n$ nodes has $\frac{n+1}{2}$ leaves. Equivalently, a tree with $2^k-1$ nodes has $2^{k-1}$ leaves.

$\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.