# Total number of nodes in a tree data structure

data-structurestree

I have a tree data structure that is L levels deep each node has about N nodes. I want to work-out the total number of nodes in the tree. To do this (I think) I need to know what percentage of the nodes that will have children.

What is the correct term for this ratio of leaf nodes to non-leaf nodes in N?

What is the formula for working out the total number nodes in the three?

Update Someone mention Branching factor in one of the answer but it then disappeared. I think this was the term I was looking for. So shouldn't a formula take the branching factor into account?

Update I should have said an estimate about a hypothetical datastructure, not the exact figure!

#### Best Solution

Ok, each node has about N subnodes and the tree is L levels deep.

``````With 1 level, the tree has 1 node.
With 2 levels, the tree has 1 + N nodes.
With 3 levels, the tree has 1 + N + N^2 nodes.
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes.
``````

The total number of nodes is (N^L-1) / (N-1).

Ok, just a small example why, it is exponential:

``````                    [NODE]
|
/|\
/ | \
/  |  \
/   |   \
[NODE]  [NODE] [NODE]
|
/|\
/ | \
``````