# how could I make a general formula for this pattern?

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

• 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? – Tanner Swett May 28 at 4:48

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

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.