How to calculate the number of nodes in an unbalanced binary tree at a given depth
If you know the number of nodes at depth 𝑑 is 𝑛, then the number of nodes at depth 𝑑 + 1 lies between 0 and 2𝑛. The minimum of 0 is reached when all those nodes at depth 𝑛 happen to be leaves, and the maximum of 2𝑛 is reached when all those nodes at depth 𝑛 happen to have two children each.
I am trying to calculate the number of nodes a tree will have at a given depth if the binary tree is not balanced.
I know that in the case of a perfectly balanced, you can use 2^d to calculate the number of nodes, where d is the depth of a tree.
Assume there is a binary tree. At the root level, it only has one node. Also, assume that the root node only has one child instead of 2. So at the next depth, there is only one node instead of 2. which means that at the next depth, there will be only two nodes instead of 4. in the next depth, there will be eight instead of 16.
So yeah is there any way I can foretell the number of nodes there will be at a given depth based on the number of nodes present or not present in the previous depth.
Any kind of answer would do if there is a mathematical formula that will help. If you know a way I could do it iteratively in breadth-first search order in any programming language that would help too.