I'm trying to find the max number of nodes in a tree that is defined as follows:
The root can have at most $2$ children.
Each subtree on the left can have at most $L$ children.
Each subtree on the right can have at most $R$ children.
I know the formula for finding the number nodes in a binary tree is $2^{n} – 1$, where $n$ is the amount of levels in the tree.
Anyone better at math than me that can help figure this out?
Best Answer
As I understand, you are looking for formula for maximal number of nodes. Let $n$ be number of levels under children of the root. Assume $n\geq 1$ (for smaller it's trivial).
On the left node has $L$ children, and each of that $L$ children has $L$ children as long as it's not a leaf ($L \cdot L$ in second tier). So on the left you have $\frac{L^{n+1}-1}{L-1}$ nodes. It's easy to calculate using informations about sum of geometric sequence.
$$1 + \sum_{i=1}^{n}L^i=1 + L \cdot\frac{1-L^n}{1-L} = \frac{L^{n+1}-1}{L-1}$$
Similarly you have $\frac{R^{n+1}-1}{R-1}$ nodes on the right. And after you include root, you receive formula.
$$1 + \frac{R^{n+1}-1}{R-1} + \frac{L^{n+1}-1}{L-1}$$